4 ms·

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 optio

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 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, Yeah so probably the better way to think about it might be with the payoff matrix. Because symmetry is actually about the strategy. That's why there are the notes about the laddering in Go. But the payoff of a symmetric game is actually when A = -A^T. So if we have a 2x2 game a symmetric zero-sum one is where the payoff matrix might look like [[0, 1], [-1, 0]] Where we're like an inverse-identity matrix (actually anti-symmetric) but the diagonals are opposite. Maybe it is best to think about this from a geometric perspective, this symmetry here (in this specific example) is a rotation matrix. That's what it does when applied to another matrix. Recall our standard form is [[cos(theta), -sin(theta)],[sin(theta), cos(theta)]]. Pretty easy to get our matrix from there if you remember that cos(90)=cos(180)=0 and sin(90)=1 but sin(180)=-1. So our angle of rotation is 180 degrees (or pi radians). You could also see that if we made the two columns vectors we'd see they pointed in opposite directions. That's the symmetry! Okay, yeah, maybe that's confusing lol. But I find it helpful to see matrices as transforms and I wish this was stated a bit more clearly and often. So now that we maybe understand that, symmetry is about a __strategy__, not a player. Because our payoff matrix is strategy based. For example, our strategy for rock-paper-scissors is to pick each outcome 1/3 of the time, which gives us this symmetric payoff. But if we pick rock every time we don't get that payoff, right? So it's actually not about who goes first or second but also includes the strategy aspect. At least that's my understanding which a lot is prompted by this conversation (thanks!) The reason I'm finding the go argument hard is thinking of a basic "entropy" based strategy (it'll serve you well in boardgames, especially when sight reading). The idea is if you don't know the best move, play the move that gives you the most future moves. It'll trick you into thinking that this strategy is actually simple, it isn't. So in the game of Go, this isn't reasonably different from making a random move! Because there are just so many. And realistically your strategy is going to be the composition of many different strategies. Like you said, pull out the decision tree but we can actually abstract this a bit more and have a decision strategy tree that's a superset to our strategy that's a response (e.g. a ladder is set up so we play the laddering strategy). The reason I'm not buying the argument isn't about the logic, it is about the possible move sets. Even with super-ko (the board cannot return to a state it has previously been at any time in the game (must be fun to keep track of...)). So forgetting about all the extras that are played in go, passing shouldn't result in a meaningful change in the number of possible strategies. But this argument might actually be an argument in favor of symmetry, not against it. Coming back to Chess, we know that game __is not__ symmetric. Why? Because white has different strategies than black. If instead the first "move" is to flip a coin and that decides who is white and who is black, then the game actually becomes symmetric. Kinda wild... I didn't read this, but a glance suggests that black dominates in smaller games http://erikvanderwerf.tengen.nl/pubdown/thesis_erikvanderwerf.pdf http://erikvanderwerf.tengen.nl/pubdown/thesis_erikvanderwer...

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 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, Yeah so probably the better way to think about it might be with the payoff matrix. Because symmetry is actually about the strategy. That's why there are the notes about the laddering in Go. But the payoff of a symmetric game is actually when A = -A^T. So if we have a 2x2 game a symmetric zero-sum one is where the payoff matrix might look like [[0, 1], [-1, 0]] Where we're like an inverse-identity matrix (actually anti-symmetric) but the diagonals are opposite. Maybe it is best to think about this from a geometric perspective, this symmetry here (in this specific example) is a rotation matrix. That's what it does when applied to another matrix. Recall our standard form is [[cos(theta), -sin(theta)],[sin(theta), cos(theta)]]. Pretty easy to get our matrix from there if you remember that cos(90)=cos(180)=0 and sin(90)=1 but sin(180)=-1. So our angle of rotation is 180 degrees (or pi radians). You could also see that if we made the two columns vectors we'd see they pointed in opposite directions. That's the symmetry! Okay, yeah, maybe that's confusing lol. But I find it helpful to see matrices as transforms and I wish this was stated a bit more clearly and often. So now that we maybe understand that, symmetry is about a __strategy__, not a player. Because our payoff matrix is strategy based. For example, our strategy for rock-paper-scissors is to pick each outcome 1/3 of the time, which gives us this symmetric payoff. But if we pick rock every time we don't get that payoff, right? So it's actually not about who goes first or second but also includes the strategy aspect. At least that's my understanding which a lot is prompted by this conversation (thanks!) The reason I'm finding the go argument hard is thinking of a basic "entropy" based strategy (it'll serve you well in boardgames, especially when sight reading). The idea is if you don't know the best move, play the move that gives you the most future moves. It'll trick you into thinking that this strategy is actually simple, it isn't. So in the game of Go, this isn't reasonably different from making a random move! Because there are just so many. And realistically your strategy is going to be the composition of many different strategies. Like you said, pull out the decision tree but we can actually abstract this a bit more and have a decision strategy tree that's a superset to our strategy that's a response (e.g. a ladder is set up so we play the laddering strategy). The reason I'm not buying the argument isn't about the logic, it is about the possible move sets. Even with super-ko (the board cannot return to a state it has previously been at any time in the game (must be fun to keep track of...)). So forgetting about all the extras that are played in go, passing shouldn't result in a meaningful change in the number of possible strategies. But this argument might actually be an argument in favor of symmetry, not against it. Coming back to Chess, we know that game __is not__ symmetric. Why? Because white has different strategies than black. If instead the first "move" is to flip a coin and that decides who is white and who is black, then the game actually becomes symmetric. Kinda wild... I didn't read this, but a glance suggests that black dominates in smaller games http://erikvanderwerf.tengen.nl/pubdown/thesis_erikvanderwerf.pdf http://erikvanderwerf.tengen.nl/pubdown/thesis_erikvanderwer...