4 ms·

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

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.
    - recursivecaveat 3y ago
      Oh yeah, in chess going 1st is 100% definitely an advantage. For example, pawn to a4 is a really bad opener because its so close to throwing away that advantage by passing your first turn. Its just that the rules permit that taking a turn can force you into a worse position than you started, and you can't prove the starting position isn't like that. So from a proof perspective the empirical truth that going first is really good is not particularly helpful. The passing thing is weird because it empirically is a bad idea, it just closes a theoretical loophole. I'm not a mathematician myself, just got into this stuff when I was working on a boardgame solver. I find it difficult to map the 'symmetric game' definition "the payoffs for playing a particular strategy depend only on the other strategies employed, not on who is playing them" onto a turn based game, but if it can work for Hex it must be compatible. If you consider a strategy to be "a decision tree for how to place stones, when I'm playing as 2nd", then there's perfect symmetry between being 1st and choosing to immediately pass, and being 2nd. The possible strategies and resulting payoffs are the same. You add on top the extra move, which the possibility of passing means is at worst neutral for 1st player, and they cannot be at a disadvantage. More intuitively for me: being allowed to pass your first move is the same as getting to pick which side you want to play. There's no way the side who can pick to play 1st or 2nd at their option can be at a forced loss to the side who just has to accept their decision. The picker would just pick the other side and now they have a forced win. (I'm always assuming above any kind of infinite-pass-standoff is a draw, and not some kind of weird other thing). If I haven't expressed my thoughts clearly enough that's probably about as well as I can manage I'm afraid.

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.
  - recursivecaveat 3y ago
    Oh yeah, in chess going 1st is 100% definitely an advantage. For example, pawn to a4 is a really bad opener because its so close to throwing away that advantage by passing your first turn. Its just that the rules permit that taking a turn can force you into a worse position than you started, and you can't prove the starting position isn't like that. So from a proof perspective the empirical truth that going first is really good is not particularly helpful. The passing thing is weird because it empirically is a bad idea, it just closes a theoretical loophole. I'm not a mathematician myself, just got into this stuff when I was working on a boardgame solver. I find it difficult to map the 'symmetric game' definition "the payoffs for playing a particular strategy depend only on the other strategies employed, not on who is playing them" onto a turn based game, but if it can work for Hex it must be compatible. If you consider a strategy to be "a decision tree for how to place stones, when I'm playing as 2nd", then there's perfect symmetry between being 1st and choosing to immediately pass, and being 2nd. The possible strategies and resulting payoffs are the same. You add on top the extra move, which the possibility of passing means is at worst neutral for 1st player, and they cannot be at a disadvantage. More intuitively for me: being allowed to pass your first move is the same as getting to pick which side you want to play. There's no way the side who can pick to play 1st or 2nd at their option can be at a forced loss to the side who just has to accept their decision. The picker would just pick the other side and now they have a forced win. (I'm always assuming above any kind of infinite-pass-standoff is a draw, and not some kind of weird other thing). If I haven't expressed my thoughts clearly enough that's probably about as well as I can manage I'm afraid.