Arnold Kling  

Solving Othello: a Follow-Up

PRINT
My Othello Career... Free Speech for Them but Not f...

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.


Comments and Sharing


CATEGORIES: Game Theory



COMMENTS (5 to date)
PrometheeFeu writes:

Hm... That depends upon your definition of solving a game. There is at least one definition that says for a game to be solved, there must be a perfect play displayed from any position. In the scenario you are describing, there is no description of perfect play once you or your opponent is up by a certain amount.

SB7 writes:

Yes, I agree with PrometheeFeu. This would give you a strong Othello player, but not a "solution" in the sense that checkers now has a solution.

You might find the Univ. of Alberta's "GAMES Group" interesting if you do not already know of them.

Finch writes:

That isn't what most people mean when they say "solved." How do you know there isn't some hidden trap? If I remember correctly, that's a lot less likely in Othello than chess, but it's a possibility, right?

If you just want to see perfect play, we've probably got an awfully good approximation of that today. But we haven't proven we have it.

Solving requires an evaluation algorithm that provably doesn't change the score from the full mini-max evaluation, like Alpha-Beta. You can't just truncate and say "close enough."

Kenton A Hoover writes:

You might try Googling "Chinook" and "checkers"...

Cryptomys writes:

I agree that what Arnold proposes would not be a rigorous solution, but it might give you the answer to a couple of interesting questions with over 95% confidence. Is Othello a draw or a win for one side or the other (probably the second player, White, if it is indeed a win)?

What is the best basic opening in Othello? There are three basic openings: the parallel, the perpendicular, and the diagnonal. Most strong players believe that the parallel opening is inferior. Whether the perpendicular or the diagonal is best is debatable. Of course, it's possible that with best play, the perpendicular and the diagonal lead to the same result.

Comments for this entry have been closed
Return to top