New paper claims that Othello / Reversi is solved
March 15, 2024 1:16 PM Subscribe
A serendipitous follow up from my previous Othello post, this new paper from Hiroki Takizawa claims that Othello is solved: "It is computationally proved that perfect play by both players lead to a draw. Strong Othello software has long been built using heuristically designed search techniques. Solving a game provides a solution that enables the software to play the game perfectly." GitHub link to C source code included (it's a modified form of Edax.)
Previously on mefi is a discussion about computers' ability to play strategy games.
Previously on mefi is a discussion about computers' ability to play strategy games.
It's generally not possible to solve a game for more than two players unless the game is pretty trivial. Imagine, for example, that you're player A, and player B is doing everything they can to throw the game to player C. If you can still win in that scenario, the game probably wasn't very interesting to start with.
posted by dfan at 2:14 PM on March 15 [3 favorites]
posted by dfan at 2:14 PM on March 15 [3 favorites]
> It's generally not possible to solve a game for more than two players unless the game is pretty trivial
A game is solved if (a) for some player, there is an algorithm that lets them win, regardless of what the other players choice of moves, or (b) you can prove no such algorithm exists.
The "easy" way to prove (b) in a two player game is to find a "perfect play" for each player that prevents the other player from winning regardless of what the other player does.
But the fact that player 3 can "throw" and let player 1 win isn't a barrier to a game being solved. It does make one technique a bit harder.
If in a 3 player game, each player can only win if one of their opponents makes a mistake, that is a solved game.
I guess it is interesting if player 3 can make a move that results in player 2 being forced to choose if player 1 or player 3 wins? Here, player 3 doesn't have a proven winning strategy, as player 2 can still make them lose. But the game isn't a draw. So the descriptions of the solution (player 1 win, player 2 win, draw) gets more complex (draw, player 1 or 2 or 3 loss, and player 1 or 2 or 3 win, are distinct possible solutions).
posted by NotAYakk at 2:39 PM on March 15 [2 favorites]
A game is solved if (a) for some player, there is an algorithm that lets them win, regardless of what the other players choice of moves, or (b) you can prove no such algorithm exists.
The "easy" way to prove (b) in a two player game is to find a "perfect play" for each player that prevents the other player from winning regardless of what the other player does.
But the fact that player 3 can "throw" and let player 1 win isn't a barrier to a game being solved. It does make one technique a bit harder.
If in a 3 player game, each player can only win if one of their opponents makes a mistake, that is a solved game.
I guess it is interesting if player 3 can make a move that results in player 2 being forced to choose if player 1 or player 3 wins? Here, player 3 doesn't have a proven winning strategy, as player 2 can still make them lose. But the game isn't a draw. So the descriptions of the solution (player 1 win, player 2 win, draw) gets more complex (draw, player 1 or 2 or 3 loss, and player 1 or 2 or 3 win, are distinct possible solutions).
posted by NotAYakk at 2:39 PM on March 15 [2 favorites]
Now do stratego! So I can I can finally beat my husband. Lockdown was a surprisingly volatile place in our home when the kids went to sleep and we pulled out the 2 player games.
posted by atomicstone at 2:48 PM on March 15 [2 favorites]
posted by atomicstone at 2:48 PM on March 15 [2 favorites]
Now we have two ways to keep WOPR from starting a nuclear war!
posted by Abehammerb Lincoln at 2:49 PM on March 15 [7 favorites]
posted by Abehammerb Lincoln at 2:49 PM on March 15 [7 favorites]
I wrote a tiny Othello clone on my Palm IIIc back in the bad old days of my call center temp job out of college, and I was working with such an artificially limited source code footprint that I had to jimmy in as concise a player 2 AI as I could. Between that constraint and me not being a particularly good Othello player to begin with, my computer player heuristic came down to:
1. If there's a corner move, make it.
2. Otherwise if there's an edge move, make it.
3. Otherwise, pick a random valid move if there is one.
4. Otherwise, pass.
It was good enough to defeat someone who had never played Othello before, but that was about it. Glad to see moderately better results have been achieved in the ensuing twenty years.
posted by cortex at 2:52 PM on March 15 [11 favorites]
1. If there's a corner move, make it.
2. Otherwise if there's an edge move, make it.
3. Otherwise, pick a random valid move if there is one.
4. Otherwise, pass.
It was good enough to defeat someone who had never played Othello before, but that was about it. Glad to see moderately better results have been achieved in the ensuing twenty years.
posted by cortex at 2:52 PM on March 15 [11 favorites]
I will pat myself on the back for my last comment in the Othello thread, where I said I don't see how a human could beat an Othello bot, as the game seems pretty cut and dried.
Play better abstracts! Or games with cards and randomness!
Stratego seems tough to solve. Connect 4 has long been solved.
posted by Windopaene at 3:32 PM on March 15 [1 favorite]
Play better abstracts! Or games with cards and randomness!
Stratego seems tough to solve. Connect 4 has long been solved.
posted by Windopaene at 3:32 PM on March 15 [1 favorite]
I mean, it’s always been Iago, right? Unless the question is “why did Iago do it?” In which case the answer is “I dunno.”
posted by GenjiandProust at 5:29 PM on March 15 [14 favorites]
posted by GenjiandProust at 5:29 PM on March 15 [14 favorites]
My dad taught me Othello on a for sure his generation board. I have a tactile and regular memory of the felt board, the plastic cover that covered your pieces. I have so many great memories of camping in state parks and playing Othello and the aforementioned Stratego with him. Beating him at SORRY! is still a hard won triumph.
I'm so lucky he's still alive. Next time we/they visit, I'm for sure looking to get my ass beat at any/every game.
posted by atomicstone at 5:40 PM on March 15
I'm so lucky he's still alive. Next time we/they visit, I'm for sure looking to get my ass beat at any/every game.
posted by atomicstone at 5:40 PM on March 15
Okay, amateur math person, so correct me if I am wrong. So they had a game which resulted in a draw, and they proved that, in this particular game, if one deviated from perfect game play, then one would either lose or draw.
That's delightful, and interesting, but I'm wondering how this particular solve translates to a more universal solve for the game.
posted by indexy at 5:55 PM on March 15
That's delightful, and interesting, but I'm wondering how this particular solve translates to a more universal solve for the game.
posted by indexy at 5:55 PM on March 15
There are two flavors of solving a game. This is the easy one: if both players do the best thing they can, it's a draw. Neither can do better by doing something different. They can, of course, do worse.
The harder kind is IIRC called "strongly solved", and it means that from any position, you know who wins if everyone plays perfectly from there on out.
The first kind gets all the press because once the correct moves are known, nobody is ever going to make an incorrect move.
posted by novalis_dt at 8:08 PM on March 15 [1 favorite]
The harder kind is IIRC called "strongly solved", and it means that from any position, you know who wins if everyone plays perfectly from there on out.
The first kind gets all the press because once the correct moves are known, nobody is ever going to make an incorrect move.
posted by novalis_dt at 8:08 PM on March 15 [1 favorite]
I did an Othello games in college as an assignment, must have been in 96 or so. I still remember the feeling I had when the "AI" started consistently beating me. I had to decide whether I sucked at Othello or was awesome at programming.
posted by Harald74 at 1:48 AM on March 16 [5 favorites]
posted by Harald74 at 1:48 AM on March 16 [5 favorites]
To clarify a what 'Solved' means in mathematics:
A game is solved if there is an algorithm that always produces the same outcome (draw, win for first mover, win for second mover) from the starting position. The claim in the article is that if both players follow the algorithm, they will draw. If either deviates from it, they will lose.
Technically that's the definition of 'Weakly Solved'. 'Strongly Solved' requires an algorithm that can achieve the same certainty from any position.
posted by Combat Wombat at 4:32 AM on March 16
A game is solved if there is an algorithm that always produces the same outcome (draw, win for first mover, win for second mover) from the starting position. The claim in the article is that if both players follow the algorithm, they will draw. If either deviates from it, they will lose.
Technically that's the definition of 'Weakly Solved'. 'Strongly Solved' requires an algorithm that can achieve the same certainty from any position.
posted by Combat Wombat at 4:32 AM on March 16
In a game with no random elements, if both players always make the same sequence of moves, they'll always get the same outcome. So I must be misunderstanding something in that definition of 'Weakly Solved', or else every such game would be weakly solved, right?
posted by rifflesby at 5:10 AM on March 16
posted by rifflesby at 5:10 AM on March 16
(Whether such an algorithm is known and proven to satisfy those requirements is a factor that seems to have been elided)
posted by polytope subirb enby-of-piano-dice at 5:22 AM on March 16 [1 favorite]
posted by polytope subirb enby-of-piano-dice at 5:22 AM on March 16 [1 favorite]
rifflesby: "Weakly solved" (in a game where the first player wins) means that if we play a full game starting from the beginning position, then I, as the first player, have an algorithm for making moves that guarantees I will win the game no matter what you, the second player, do.
Basically, read "always produces" in Combat Wombat's definition as "is guaranteed to produce".
posted by dfan at 6:38 AM on March 16 [1 favorite]
Basically, read "always produces" in Combat Wombat's definition as "is guaranteed to produce".
posted by dfan at 6:38 AM on March 16 [1 favorite]
I must be misunderstanding something in that definition of 'Weakly Solved', or else every such game would be weakly solved, right?
Suppose we sit down to play a game with no chancy elements. We play a sequence of moves and come to a draw. If we play those exact moves again, we'll get the same result. But in most games, there's more than one move that can be made from the starting position. (In chess, for example, there are 16 pawn moves and 4 knight moves allowed from the starting position.) Game solutions are one-sided: they are rules prescribing how a single player is to play, leaving it open how the other player plays. Usually, one assumes the opponent plays perfectly. In some games, such as tic-tac-toe, perfect play from both players results in a draw. But of course, if my opponent doesn't play perfectly, I might be able to win! In some games, the first player can guarantee a win, not just a draw, regardless of what the other player does. Chomp is a typical example. And in some games, the second player can guarantee a win. Maharajah and the Sepoys is an example.
A game is solved (for a player) if there is an algorithm that will win or draw the game regardless of how the opponent plays. So, if in our game, I had a solution, then it's not just that I can win or draw the game when you play in exactly the way you did. Rather, for any sequence of moves you make, I have a "matching" sequence that results in either a win (for me) or a draw.
Stepping back a bit, there are a few different things that one might show about a game. One might prove an existence result: namely, that there is a solution. Classically, doing this is not the same as actually having a solution. It's sort of like finding lots of evidence that a pirate buried a treasure. You know that there is a treasure, but you don't have the treasure.
Going one step further, you might actually have a solution in the sense of having an algorithm that guarantees a specific, predesignated result starting from the initial game configuration. You might have a solution without knowing that you have a solution. For example, you invented a strategy that seems good, but you haven't tested it on all possible branches from the initial game configuration. If you also have a proof that your algorithm works as advertised, then you have a proof that there is a solution, and (plausibly) you know that you have a solution. But again, you might have a proof that there is a solution without actually being able to produce a solution.
Going even further, you might have a solution in the sense of having an algorithm that guarantees a specific, predesignated result starting from any admissible game configuration. And you might have solutions from some admissible starting positions but not others. For example, we don't have a solution for chess, but we do have lots of winning or drawing strategies from specific admissible game configurations -- positions one might reach in playing a game of chess. (One way to think about such strategies is as solutions to variant games where the movement rules are the same as in the original game but the initial game configuration is different.)
posted by Jonathan Livengood at 7:55 AM on March 16 [2 favorites]
Suppose we sit down to play a game with no chancy elements. We play a sequence of moves and come to a draw. If we play those exact moves again, we'll get the same result. But in most games, there's more than one move that can be made from the starting position. (In chess, for example, there are 16 pawn moves and 4 knight moves allowed from the starting position.) Game solutions are one-sided: they are rules prescribing how a single player is to play, leaving it open how the other player plays. Usually, one assumes the opponent plays perfectly. In some games, such as tic-tac-toe, perfect play from both players results in a draw. But of course, if my opponent doesn't play perfectly, I might be able to win! In some games, the first player can guarantee a win, not just a draw, regardless of what the other player does. Chomp is a typical example. And in some games, the second player can guarantee a win. Maharajah and the Sepoys is an example.
A game is solved (for a player) if there is an algorithm that will win or draw the game regardless of how the opponent plays. So, if in our game, I had a solution, then it's not just that I can win or draw the game when you play in exactly the way you did. Rather, for any sequence of moves you make, I have a "matching" sequence that results in either a win (for me) or a draw.
Stepping back a bit, there are a few different things that one might show about a game. One might prove an existence result: namely, that there is a solution. Classically, doing this is not the same as actually having a solution. It's sort of like finding lots of evidence that a pirate buried a treasure. You know that there is a treasure, but you don't have the treasure.
Going one step further, you might actually have a solution in the sense of having an algorithm that guarantees a specific, predesignated result starting from the initial game configuration. You might have a solution without knowing that you have a solution. For example, you invented a strategy that seems good, but you haven't tested it on all possible branches from the initial game configuration. If you also have a proof that your algorithm works as advertised, then you have a proof that there is a solution, and (plausibly) you know that you have a solution. But again, you might have a proof that there is a solution without actually being able to produce a solution.
Going even further, you might have a solution in the sense of having an algorithm that guarantees a specific, predesignated result starting from any admissible game configuration. And you might have solutions from some admissible starting positions but not others. For example, we don't have a solution for chess, but we do have lots of winning or drawing strategies from specific admissible game configurations -- positions one might reach in playing a game of chess. (One way to think about such strategies is as solutions to variant games where the movement rules are the same as in the original game but the initial game configuration is different.)
posted by Jonathan Livengood at 7:55 AM on March 16 [2 favorites]
Abehammerb Lincoln, there's a couple options!
Checkers was solved in October 2007 (perfect play yields a draw).
And if we don't want to give WOPR the wrong idea,
Connect Four was solved in October 1988 by two separate folks; perfect play yields a first player win. Pretty sneaky sis, indeed.
I'm really waiting for somebody to figure out Ultimate Tic-Tac-Toe, which has been my "distract unruly kids in a restaurant" move for a few years now.
posted by adekllny at 8:40 AM on March 19
Checkers was solved in October 2007 (perfect play yields a draw).
And if we don't want to give WOPR the wrong idea,
Connect Four was solved in October 1988 by two separate folks; perfect play yields a first player win. Pretty sneaky sis, indeed.
I'm really waiting for somebody to figure out Ultimate Tic-Tac-Toe, which has been my "distract unruly kids in a restaurant" move for a few years now.
posted by adekllny at 8:40 AM on March 19
« Older The head on the car is a dream | Stand In Pride Newer »
This thread has been archived and is closed to new comments
posted by Strange Interlude at 1:28 PM on March 15 [5 favorites]