From:  (Joel F Feinstein)
Subject:        Re: 6x6 Othello
Keywords:       computer Othello
Organization:   Maths Dept., Nottingham University, UK.
Date:           Tue, 8 Jun 93 17:50:51 GMT

Jan Eric Larsson writes:
>Joel feinstein writes:
>>I now have an optimal sequence for 6x6 Othello, if anyone
>>is interested. The second player wins 20-16.
>I would be very happy if you would post your results. If you have some
>more information, like time used, how you did it, search method, ect.,
>I am sure it would be appreciated.

My strategy for solving 6x6 Othello was to modify my 8x8 player to
play 6x6, using a similar mid-game strategy in terms of corner regions
and potential mobility (aim: maximize the number of empty squares
touching opponents discs) to the 8x8 version.

In the following please note that, in my notation, the top left square 
of the 6x6 Othello board is denoted by b2, for reasons explained in a 
previous posting.

My endgame analyser uses short midgame searches to order the moves for
its (unsophisticated) alpha-beta search. I was surprised to find that 
the program could solve win-loss-draw with 29 empty squares in a day in most 
cases (in 8x8 it can only do 25-27 in this time). So, with no further thought
required I was able to show that the second player had a forced win using about
1.5 weeks cpu time on our silicon graphics crimson chip.
This seems to have been a little lucky: the "parallel opening"
(1.d3 2.e3) turns out to be VERY complicated, and I still don't know
who wins. But it didn't take too long to show that white can not win
by more than 4, which turns out to be critical (see below). The "diagonal" 
opening 1.d3 2.c3 is an easy loss, and only took one night. The remaining 
"perpendicular" opening, 1.d3 2.c5, wins by 4.  (This calculation took 
two weeks of cpu time: much quicker than I had expected. It helped
that I guessed that the score would be strictly between 18-18 and 21-15.
I was again fortunate that the return value was inside my window).
The two calculations together required that about 60-70,000,000,000 
positions be evaluated. I expect that more sophisticated search techniques 
could reduce this figure by a large factor.

By symmetry, black's first move is forced. Thus white can use the following
book to achieve a won position after three moves each. I do not claim that 
these lines are optimal for white. 

d3 c5 b6 e3 f5 e6
            f4 d2 
            d6 c4 
            f2 d2 
            f6 d2 
            f3 d2 
      c6 e3 b5 d2 
            c4 b5 
            f5 d2 
            f3 f4 
      d6 e3 b4 d2 
            f4 d2 
            b5 d2 
            f5 f4 
            f3 e2
      e6 d2 c2 b2 
            c3 e3 
            c4 b5 
            b5 f4 
            c6 f4
      f6 d2 c4 b5 
            c3 f5 
            c6 f5 
            c2 b2 
            b5 f4 

Joel Feinstein (