Solving Othello: a Follow-Up
This is an off-topic response to comments on my earlier off-topic post on the board game Othellotm. I believe that it could be solved using today’s computers, by truncating the decision tree whenever a player is in a clear losing position.One heuristic would be to truncate once a clear winning position has been established. By a winning position, I mean not that every subsequent node on the tree has been searched, but a position that is surely a win nonetheless. Imagine a chess game where one player is down a queen with no compensation of either material or position.
In Othello, as in chess, it is possible to be dead out of the opening after just a handful of moves. More generally, I found in experiments with the computer program Zebra (mentioned in the previous post) that whenever the program estimated an advantage of 5 discs or more, this advantage was never overcome. This is a very narrow advantage, so truncating at 5 discs would eliminate the vast majority of possible Othello sequences.
There are still a large number of sequences where throughout the game neither side obtains a 5-disc advantage. I do not know whether this set of sequences is too large to search by brute force. If it is, one could set the cutoff at a 4-disc advantage, or at a 3-disc advantage. However, there is some risk that a narrow cutoff could lead you to overlook a sequence that actually works. That is, you risk treating a position as hopeless for black when subsequent analysis could show that to be wrong.
If I were out to find a solution for the game, I would make a lot of use of the database of played games. You could have Zebra go through all games in the database between top-level players (including computers) and at move 40 for each game solve for the perfect endgame. This gives you “true” scores for the games at move 40 (as opposed to actual scores, which may be the result of mistakes). The probability is very high that one of those sequences of 40 moves, along with the perfect endgame, is the solution to Othello.
If the perfect game has already been played, then of our database of games with true scores, we need only look at close games–I would say games that are decided by 2 discs or less.
Now that we have narrowed down the database to games with true scores that are close, we need to examine alternatives for the first forty moves. You will find that the games can be grouped into families based on openings. Within a family, there will be identical sequences of moves for 15 moves or more. My guess is that there will be more than 10 viable opening families, but fewer than 100.
Next, you want to have Zebra go back and analyze the moves between moves 15 and 40 in this database, working backwards. That is, for each game, have Zebra start at move 40 to try to find a better move. If none is found, go back to move 39, and so on, until you reach the point (move 15 or so) where all the games in the family start from the same position.
Once all of the midgame moves have been optimized by Zebra in this fashion, you have a set of pseudo-true-score games. You then do a brute-force min-max search among these games. For example, suppose that in the database, the pseudo true scores for the sequences of moves at 16 and 17, by white and black, respectively, is as follows (white’s score in parentheses:
16 c8, g6 (+2)
16 c8, g4 (0)
16 d8, c8 (3)
16 d8, g4 (-1)
Here, white should choose c8, since with black’s best response (according to the database), white gets a draw, whereas with d8 black’s response leads to a loss for white.
This min-max search has to operate like an engame search, with forward and backward min-max. However, the computer is not searching through all possible moves, but only through the branches of the tree actually in the database.
Finally, you have to throw out all opening families where one side achieves a sub-optimal outcome. If the best outcome is a draw, then you have refuted any opening family where one player necessarily loses even with best play.
My conjecture is that there will be multiple solutions with the same value, and that value will be either +2 for white or 0. There may be a dozen families of openings that lead to the optimum value, and each opening family may have 10 to 20 subsequent variations that lead to the optimum value.
I would tend to bet against Black having a win in the optimum game. White moves second in Othello, and that is potentially an advantage because of what the British players dubbed parity. The last move usually flips more pieces than the next-to-last move. If white can divide the board into regions of even squares, then white can get the last move in each region (“playing for parity”), which is usually devastating. However, this advantage is not guaranteed for white. Black can gain parity by creating an odd empty region where white has no moves. And there are positions where parity is not the dominant factor. Overall, the databases suggest that white’s advantage, if there is one, is not as large as we once thought.