4 ms·

What mathematics was AlphaGo solving? What do you mean by solving there?

by RandomLensman 3y ago

dimask 3y ago
Proving that the first player has a winning strategy, or the optimal strategy for both players leads to draw.
- falcor84 3y ago
  Just to nitpick, while unlikely, it is theoretically possible that the second player has a winning strategy
  - k2enemy 3y ago
    To nitpick a little further, it actually is not possible that the second player has a winning strategy. For that to be the case, P2 would need a winning path of play no matter what P1's first move is. Suppose that P1 passes on their first move (which is a valid move). Then P2 has a winning path of play in which they put down the first stone. But P1 could have made that move and then they would be on the winning path.
    - falcor84 3y ago
      Good point, I actually wasn't that they could pass the first move
    - godelski 3y ago
      I'm not a game theorist, in RL, nor a big Go player; but I am having a hard time finding this argument convincing. Isn't the whole reason Go is impressive is because the enormous set of possible moves? Like we know that no computer could run ever game in the lifetime of the universe were it to even perform millions of moves a second. So of the I understand this number to be north of 10^500 for possible legal and playable games. So the difference of 1 doesn't seem meaningful. Is there something I'm missing or a more convincing argument? Because even if player 1 always locks out 90% of those possible future moves, that's still an absurdly large search space and it doesn't seem like it is meaningfully different.
      - recursivecaveat 3y ago
        It's a proof by contradiction, like the halting problem proof. It doesn't rely on the actual playable games at all, but what the existence of a winning strategy would imply. If there was a guaranteed winning strategy for player 2 it would be contradictory because player 1 could execute it by passing their first turn then using the winning P2 strategy. In that game both players can't be guaranteed to win, so there must be some flaw in P2's supposed guaranteed win strategy. https://en.m.wikipedia.org/wiki/Strategy-stealing_argument https://en.m.wikipedia.org/wiki/Strategy-stealing_argument
        godelski 3y ago
        I am familiar with strategy stealing and things like tit-for-tat. But even the wiki article you linked suggests that Go is not a symmetric game, which is the requisite condition for strategy stealing to work (which was my underlying belief albeit (very) poorly worded). The wiki suggests both ladder and ko fights create an asymmetry as well as central control. Not to mention Komi explicitly making it asymmetric. First player does not always have the advantage. Nim is the best example where the setup can either be the first player winning game (nim-sum of the sizes of the heaps is not zero) or the second. My understanding is also that Chess (another perfect information turn-based game) is not shown solved or even has proven first player advantage (though in practice it looks so). So I get the argument, I just don't buy it. I would be inclined to lean towards that direction, but it's a tough claim theoretically and probably not meaningful in practice (unless a generalized strategy such as strategy stealing can be employed otherwise a lookup table is impractical as it'd contain more bits than atoms in the universe even for 100 move games). I think we have to consider far more than strategy-stealing which is not even a generalizable strategy to two-person perfect information turn-based games. https://en.wikipedia.org/wiki/Nim#Proof_of_the_winning_formula https://en.wikipedia.org/wiki/Nim#Proof_of_the_winning_formu...
        recursivecaveat 3y ago
        The passing is the important part. In chess you can't pass so going first might be bad, you could be the first to reach a forced zugzwang. If you have the option of passing your first turn, then having a turn before the 2nd player gets to go is at worst neutral for you. Likewise in Nim you can't pass and taking your turn might be bad for you unlike Hex.
  - daveguy 3y ago
    I would assume this is possible for any sufficiently complex game. Would you mind answering a few questions from someone near-completely ignorant about Go? Does second mover in Go have some sort of artificial benefit in scoring or playing? As in -- is there something to compensate for moving second? On the face it seems like first mover would have an advantage in any turn-based game. But maybe, in some games, seeing an opponent's strategy is more helpful than executing the strategy. Also, are there examples of real games where second mover can always win? (Real as in, not made up with weird rules just to demonstrate it's possible.)
    - gizmo686 3y ago
      > Does second mover in Go have some sort of artificial benefit in scoring or playing? As in -- is there something to compensate for moving second? Yes. The second player typically gets an extra 6.5 or 7.5 points.

What mathematics was AlphaGo solving? What do you mean by solving there?

dimask 3y ago

Proving that the first player has a winning strategy, or the optimal strategy for both players leads to draw.

falcor84 3y ago
Just to nitpick, while unlikely, it is theoretically possible that the second player has a winning strategy
- k2enemy 3y ago
  To nitpick a little further, it actually is not possible that the second player has a winning strategy. For that to be the case, P2 would need a winning path of play no matter what P1's first move is. Suppose that P1 passes on their first move (which is a valid move). Then P2 has a winning path of play in which they put down the first stone. But P1 could have made that move and then they would be on the winning path.
  - falcor84 3y ago
    Good point, I actually wasn't that they could pass the first move
  - godelski 3y ago
    I'm not a game theorist, in RL, nor a big Go player; but I am having a hard time finding this argument convincing. Isn't the whole reason Go is impressive is because the enormous set of possible moves? Like we know that no computer could run ever game in the lifetime of the universe were it to even perform millions of moves a second. So of the I understand this number to be north of 10^500 for possible legal and playable games. So the difference of 1 doesn't seem meaningful. Is there something I'm missing or a more convincing argument? Because even if player 1 always locks out 90% of those possible future moves, that's still an absurdly large search space and it doesn't seem like it is meaningfully different.
    - recursivecaveat 3y ago
      It's a proof by contradiction, like the halting problem proof. It doesn't rely on the actual playable games at all, but what the existence of a winning strategy would imply. If there was a guaranteed winning strategy for player 2 it would be contradictory because player 1 could execute it by passing their first turn then using the winning P2 strategy. In that game both players can't be guaranteed to win, so there must be some flaw in P2's supposed guaranteed win strategy. https://en.m.wikipedia.org/wiki/Strategy-stealing_argument https://en.m.wikipedia.org/wiki/Strategy-stealing_argument
      - godelski 3y ago
        I am familiar with strategy stealing and things like tit-for-tat. But even the wiki article you linked suggests that Go is not a symmetric game, which is the requisite condition for strategy stealing to work (which was my underlying belief albeit (very) poorly worded). The wiki suggests both ladder and ko fights create an asymmetry as well as central control. Not to mention Komi explicitly making it asymmetric. First player does not always have the advantage. Nim is the best example where the setup can either be the first player winning game (nim-sum of the sizes of the heaps is not zero) or the second. My understanding is also that Chess (another perfect information turn-based game) is not shown solved or even has proven first player advantage (though in practice it looks so). So I get the argument, I just don't buy it. I would be inclined to lean towards that direction, but it's a tough claim theoretically and probably not meaningful in practice (unless a generalized strategy such as strategy stealing can be employed otherwise a lookup table is impractical as it'd contain more bits than atoms in the universe even for 100 move games). I think we have to consider far more than strategy-stealing which is not even a generalizable strategy to two-person perfect information turn-based games. https://en.wikipedia.org/wiki/Nim#Proof_of_the_winning_formula https://en.wikipedia.org/wiki/Nim#Proof_of_the_winning_formu...
        recursivecaveat 3y ago
        The passing is the important part. In chess you can't pass so going first might be bad, you could be the first to reach a forced zugzwang. If you have the option of passing your first turn, then having a turn before the 2nd player gets to go is at worst neutral for you. Likewise in Nim you can't pass and taking your turn might be bad for you unlike Hex.
- daveguy 3y ago
  I would assume this is possible for any sufficiently complex game. Would you mind answering a few questions from someone near-completely ignorant about Go? Does second mover in Go have some sort of artificial benefit in scoring or playing? As in -- is there something to compensate for moving second? On the face it seems like first mover would have an advantage in any turn-based game. But maybe, in some games, seeing an opponent's strategy is more helpful than executing the strategy. Also, are there examples of real games where second mover can always win? (Real as in, not made up with weird rules just to demonstrate it's possible.)
  - gizmo686 3y ago
    > Does second mover in Go have some sort of artificial benefit in scoring or playing? As in -- is there something to compensate for moving second? Yes. The second player typically gets an extra 6.5 or 7.5 points.