6 ms·

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 sequen

by cvoss 3y ago

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.

charcircuit 3y ago
>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.
- lcuff 3y ago
  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.
  - deleted 3y ago
    [deleted]
- deleted 3y ago
  [deleted]
- deleted 3y ago
  [deleted]
- SonOfLilit 3y ago
  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.
  - leoff 3y ago
    > 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.
    - bluGill 3y ago
      You don't, you trust that God has proved.
      - kreetx 3y ago
        I don't get then, how the paper "solves Othello": how does it determine the perfect game (why is it perfect)?
        bluGill 3y ago
        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.
    - Scarblac 3y ago
      Not the perfect game, a perfect game. There will be a huge number of them, many of them very boring and unremarkable
  - 3y ago
- tromp 3y ago
  > 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.
  - NooneAtAll3 3y ago
    > Such is the difference between weakly and strongly solving. no, you described difference between storing the result and not storing it strongly solving means allowing arbitrary amount of mistakes from either player before giving to the solver
- foota 3y ago
  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.
akoboldfrying 3y ago
>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.
hgfghui7 3y ago
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.

by cvoss 3y ago

charcircuit 3y ago

>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.

lcuff 3y ago
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.
- deleted 3y ago
  [deleted]
deleted 3y ago
[deleted]
deleted 3y ago
[deleted]
SonOfLilit 3y ago
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.
- leoff 3y ago
  > 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.
  - bluGill 3y ago
    You don't, you trust that God has proved.
    - kreetx 3y ago
      I don't get then, how the paper "solves Othello": how does it determine the perfect game (why is it perfect)?
      - bluGill 3y ago
        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.
  - Scarblac 3y ago
    Not the perfect game, a perfect game. There will be a huge number of them, many of them very boring and unremarkable
- 3y ago
tromp 3y ago
> 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.
- NooneAtAll3 3y ago
  > Such is the difference between weakly and strongly solving. no, you described difference between storing the result and not storing it strongly solving means allowing arbitrary amount of mistakes from either player before giving to the solver
foota 3y ago
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.

akoboldfrying 3y ago

>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.

hgfghui7 3y ago

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.