This paper "weakly solves" Othello. That means that we know for the initial board state both 1) the final win/lose/draw outcome (it's a draw), and 2) the sequence of moves that should be taken by perfect players to get there (Figure 1, right).
In particular, the paper does not "strongly solve" Othello. If you have an arbitrary board state, 1) and 2) are are not necessarily known for it. That means it's still possible to win a game by intentionally deviating from the perfect sequence and betting on the fact that your opponent doesn't know how to recover.
>That means it's still possible to win a game by intentionally deviating from the perfect sequence
Someone with perfect strategy would have an answer for any deviation. Playing imperfectly would likely get you into a losing position. There is no way to go from a game being drawn if played perfectly to being winning if the then loser were to be using perfect strategy.
I agree. As a nuance, (and I'm not an Othello player, but a chess player) in many positions in chess, there are many moves that, while not the best, are just slightly worse. Finding the 'refutation' for a weaker move is the measure of the strength of a player, and playing a few slightly weaker moves in a row will almost certainly take even high level players out of 'book' (the memorized sequence of best moves). At that point, the strength of the players becomes important, as opposed to how much they have memorized. The strategy, then, is to have a _slightly_ worse position from which one can recover and go on to win. Obviously, if the opponent plays perfectly, it is either a win for him or a draw. Typically the 'slightly weaker' move still keeps the game a draw. The advantage is not a game-winning sized advantage. I wonder if in Othello there are positions where there are multiple possible moves which 'preserve' the draw.
No, the paper only "weakly solves", so it doesn't give a perfect strategy of the type you talk about.
Imagine finding a pamphlet written by God that contains a listing of a perfect game of chess. Armed with it, you will still lose easily to Magnus Carlsen. He will deviate fro| the sequence and you won't know the perfect responses to his moves.
> Imagine finding a pamphlet written by God that contains a listing of a perfect game of chess
How would you go to prove that this is the perfect game of chess, if you didn't explore all of it's possible sequences? If they did solve the game, there's no way around knowing all possible outcomes - starting from a fixed given position.
The claim (see other threads, it is not clear if the paper really shows this) is that you can follow their plan or any deviation from it known results. That is no matter what I play if you understand their paper you can ensure you don't lose. If I also know their paper I can force a draw, but I won't win.
A "weak solution" demonstrates perfect play from the initial state and merely implies the existence of a perfect strategy for the entire tree of game states, but, crucially, need not actually produce said strategy. Doing so would be a "strong solution."
An "ultra-weak solution" is even less. It gives the win/lose/draw outcome of the perfect strategy, without producing that strategy, nor even producing the game of perfect play from the initial state.
This is all covered in the second paragraph of the paper's introduction.
And if a strategy for perfect play only from the initial position is a strong solution, then what do you call the even more strongly solved case of a strategy for perfect play from any position?
The second paragraph of the paper isn't super specific about its definition for "weakly solved", but I read it as agreeing with my statement. It also calls checkers "weakly solved", a game for which a strategy to beat any possible move is known.
>He will deviate fro| the sequence and you won't know the perfect responses to his moves.
Even if you don't know the moves you will know that you are in a winning / drawn position. Magnus can not find a way to get to a winning position unless you make a mistake.
That'll be very little help if the perfect game you have starts with 1.e4, but Magnus plays 1.d4. Yes, you're not losing, congratulations. You're still on your own against Carlsen now.
You can just evaluate whether or not a given move will change from a +1 or 0 position to a 0 or -1 position and play it from there.
Perfect play in a perfect game means that the objective won't change - in optimal control theory this is called Pontryagin's Maximum Principle or the Bellman optimality criteria. A "value to go" function is enough to find the optimal solution.
Yes, but we were talking about a scenario where someone was just given the moves of a single perfect game. Not an oracle that gives you the -1/0/+1 of any position.
Weakly solving a game requires a proof of optimality, which means an evaluation of all variations to prove their value. A sequence of moves in one perfect game isn't weakly solving a game.
> Someone with perfect strategy would have an answer for any deviation.
Someone verified there is a perfect strategy, using tons of computational resources and lots of time. The game tree they explored may have millions of billions of nodes, of which only the top layers could be saved.
To use a perfect strategy in an actual game, you need to have it stored in some format that allows near-real time lookups.
Such is the difference between weakly and strongly solving.
EDIT: Strongly solving goes beyond the latter, requiring real-time best play from arbitrary positions.
The author isnt claiming it's possible to win against a perfect opponent, but rather, all perfect play scenarios end in a draw. If both players either can't play perfectly, or choose to play imperfectly, then it moves into unknown territory and either side can force a win.
This does have to be mutual though, if only one side plays imperfectly, then the other can always force at least a draw.
So if you know the other side is incapable of playing perfectly, it could be rational to deviate.
>That means it's still possible to win a game by intentionally deviating from the perfect sequence
This part is not correct. If the arbitrary board state you start from is reachable from the fixed opening state given that the other player plays perfectly, then weak-solvedness means the other player can force whatever (a draw, in this case). If not, then the question is open. I don't know Othello, but an example of a chess position that is not reachable from the standard opening position is one where White has 8 pawns (so none have been promoted) but two bishops on white squares -- such a position can never arise through a legal sequence of moves. If we pretend for a moment that chess has been weakly solved as a draw, another example would be a position where White has only its king left, while Black has two rooks -- in this situation, Black can force a win, which implies that this is not a position that could ever arise under perfect play from the standard opening position, since that has already been proven to always result in a draw.
I found it helpful to (re-)derive what "forcing a draw" actually means, maybe you will too: Player 1 can force a draw from board position B in k moves or less iff, on their turn, (1) it is already a draw or a win for them, or (2) k >= 1 and they can play a move that draws or wins immediately, or (3, the inductive case) k >= 2 and they can play a move such that, for every legal move that player 2 could then play, player 1 can force a draw or win from the resulting board position in k-2 moves or less.
This is a misunderstanding. To give an example. A perfect 1.e4 player needs a response to every possible move including 1.. f6. But he doesn't need to know how to respond to 1. d4 d5 because he avoids ever ending up in that position.
In particular, the paper does not "strongly solve" Othello. If you have an arbitrary board state, 1) and 2) are are not necessarily known for it. That means it's still possible to win a game by intentionally deviating from the perfect sequence and betting on the fact that your opponent doesn't know how to recover.