3 ms·

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 o

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.
      - godelski 3y ago
        Sorry, I'm not quite following, there seems to be a disconnection. First, I thought going first in chess is generally considered an advantage. Even the wiki article states that. Or at least says there's a 10% increased win rate. Second, I still don't get why passing is the important aspect. I thought the important aspect is symmetry. I mean I can understand this in nim since that symmetry is that killer aspect that makes for the easy analysis of a solution. When I said I'm not a game theory person I didn't mean I have no game theory experience but that's not what I study. I'm on the mathy side of ML but not so much in RL. You can use math with me if that makes things easier (in fact, I love math. Please do. RL notation doesn't scare me but rather weirds me out that it scares others) because I think we're getting lost in the conditions.

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.
    - godelski 3y ago
      Sorry, I'm not quite following, there seems to be a disconnection. First, I thought going first in chess is generally considered an advantage. Even the wiki article states that. Or at least says there's a 10% increased win rate. Second, I still don't get why passing is the important aspect. I thought the important aspect is symmetry. I mean I can understand this in nim since that symmetry is that killer aspect that makes for the easy analysis of a solution. When I said I'm not a game theory person I didn't mean I have no game theory experience but that's not what I study. I'm on the mathy side of ML but not so much in RL. You can use math with me if that makes things easier (in fact, I love math. Please do. RL notation doesn't scare me but rather weirds me out that it scares others) because I think we're getting lost in the conditions.