Nitpicking—but actually in Go, multiple moves may have the same (maximal) value—and go is normally played with either a “ko” rule which says that the location of the last move played can make a difference—or a “superko” rule—in which case the entire history of the board can matter.
In principle, every configuration of a Go board has a single “best next move”. The story of previous plays should not matter to determine future plays! And that’s probably how it would be if Go was played by planet-sized computers who could work out all possible games arising from that situation, and just play the best move every move.
Nitpicking—but actually in Go, multiple moves may have the same (maximal) value—and go is normally played with either a “ko” rule which says that the location of the last move played can make a difference—or a “superko” rule—in which case the entire history of the board can matter.
The superko rule can be reinterpreted so that each move is considered to be showing an entry in an immutable look-up table for “my move in this game given this (historyless) position” (something like the loop shortcut rules in Magic: the Gathering). If the look-up table is immutable, repeating a position would create a loop. If “best next move” is defined so that a loop is worse than a loss, and the other player’s look-up table is known, then it would not be possible for a perfect player to have a look-up table that caused a loop. In some other situations, breaking the superko rule with only “best next moves” would entail circular preferences, so that a perfect player would never want to break superko. In that case, the history of the board wouldn’t matter for defining the best next move for a given configuration. But maybe in some situations, perfect players who played by showing entire immutable look-up tables at the start of the game, in a go game without a superko rule, might use mixed strategies with a nonzero probability of a loop. Perfect players with source code access might get into games of timeless chicken.
Yes, multiple moves with the same value are easily found in the opening—trivially from the symmetries on an empty board, and even after a few moves—and in the endgame, where the exact value of moves can be computed and is typically in single-digit points.
In the midgame though, wouldn’t it be much more surprising to find two or more moves for one side which have exactly the same value—more than one “best move”—as all the symmetries have pretty much vanished by then ? I’ll admit I haven’t considered that deeply, just assumed it true.
The superko rule doesn’t make much difference to my point above; it is only damaging if there is more than one ko going on, which is relatively rare (but not unheard of). Even in that case it’s not the “entire” history of the board which is entangled together, but only a sub-history in which all moves consist of passing or taking back ko points. As soon as you add a stone somewhere (for instance by making a ko threat), superko no longer applies, it’s a different position.
If there is only one ko, you only need to include its status in the position’s description per AllanCrossman’s suggestion below.
In the midgame though, wouldn’t it be much more surprising to find two or more moves for one side which have exactly the same value—more than one “best move”—as all the symmetries have pretty much vanished by then?
The number of possible scores is limited by the size of the board. The number of available moves is also on the order of magnitude of the size of the board. The birthday paradox says that there is very likely to be a collision. Even more so since the scores aren’t evenly distributed.
It’s somewhat harder to estimate how often the best move will be one of the ties. Equally matched good players tend to end up with single digit (delta-)scores, which greatly reduces the range, and I have no particular reason to expect optimal play to differ in that respect. But if I invoke that statistic, then I also have to reduce the domain to however many moves said players would be unsure between, which I don’t know.
But the only special value mentioned on those pages, = { 0 | 0 }, is not a surreal number. It’s a combinatorial game, and every surreal number is a combinatorial game, but 0 ≤ 0, making non-numeric.
Also, while values of fragments of Go games are best treated as combinatorial games, the final value of a Go game is always simply an integer (or even an element of the set {WIN, DRAW, LOSS}), and therefore so will the maximin.
The other infinitesimals listed on that page were: UP, DOWN, UPSTAR, DOWNSTAR, TINY, MINY.
The idea that you can subtract the maximin of a move with the maximin of passing to produce move values is unfortunately not correct, due to subtleties over who gets to play last.
Move values are surreal numbers. That isn’t an artefact designed to cope with partial games, it’s equally true of complete games.
The point is not trivial to understand—but it is relatively easy to see that the conclusion (that go move values are not integers) is correct. To do that, simply work through the whole board example given here:
Who said anything about subtracting the value of passing? Passing is just another move, and has no inherent privilege over the other ~200 available moves. Ah, that’s where I was confused by your terminology: you speak of the value of a board state, which must account for what happens when either player plays on it, and passing doesn’t affect the board; whereas I was thinking of the value of a game state including whose turn it is, and passing transitions to a different game state. The former is more natural if you’re analysing partial games, and the latter is more natural if you’re brute-forcing maximin.
Auction Go is then a different game, some of whose moves are bidding in the auction rather than placing stones on the board. If you can bid fractional points, then the score is fractional, so move values can be too; and likewise for surreals or any other number system. The example you linked shows that changing the set of available bid-moves can change the outcome.
It appears that in the variation they’re using, which they call Auction Go, weird stuff occurs in which players can skip turns and stuff. Ordinary Go is the sort of game where turns simply alternate. I still think that game values in ordinary Go are always integers.
Auction go defines what “the value of a move” means. It is the smallest number of captures a perfect player would be prepared to accept as a payment for passing.
To calculate the value of a move, you have to compare moving with taking some kind of null action. That typically involves passing. Without passing (or something similar) there seems to be no way to measure the value of a move empirically.
This explains what I mean by “the value of a move”. However, I am no longer clear on what you mean by the term. You have some method of calculating move values which does not involve comparing to passing (or similar)? What do you mean by the term?
That’s totally non-standard. Nobody else means that by the term. What if you are winning by 100 points? The value of filling a dame is then 100 points?!? If that is your definition, then no wonder we disagree.
Technically, superko deals with the whole history of the board. Repeated positions don’t only arise from single-stone captures—there are other ways of doing it—e.g. see:
Nitpicking—but actually in Go, multiple moves may have the same (maximal) value—and go is normally played with either a “ko” rule which says that the location of the last move played can make a difference—or a “superko” rule—in which case the entire history of the board can matter.
That information could however be considered part of the current position.
The superko rule can be reinterpreted so that each move is considered to be showing an entry in an immutable look-up table for “my move in this game given this (historyless) position” (something like the loop shortcut rules in Magic: the Gathering). If the look-up table is immutable, repeating a position would create a loop. If “best next move” is defined so that a loop is worse than a loss, and the other player’s look-up table is known, then it would not be possible for a perfect player to have a look-up table that caused a loop. In some other situations, breaking the superko rule with only “best next moves” would entail circular preferences, so that a perfect player would never want to break superko. In that case, the history of the board wouldn’t matter for defining the best next move for a given configuration. But maybe in some situations, perfect players who played by showing entire immutable look-up tables at the start of the game, in a go game without a superko rule, might use mixed strategies with a nonzero probability of a loop. Perfect players with source code access might get into games of timeless chicken.
Right—if you are prepared to define the term “position” to mean something rather counter-intuitive.
Yes, multiple moves with the same value are easily found in the opening—trivially from the symmetries on an empty board, and even after a few moves—and in the endgame, where the exact value of moves can be computed and is typically in single-digit points.
In the midgame though, wouldn’t it be much more surprising to find two or more moves for one side which have exactly the same value—more than one “best move”—as all the symmetries have pretty much vanished by then ? I’ll admit I haven’t considered that deeply, just assumed it true.
The superko rule doesn’t make much difference to my point above; it is only damaging if there is more than one ko going on, which is relatively rare (but not unheard of). Even in that case it’s not the “entire” history of the board which is entangled together, but only a sub-history in which all moves consist of passing or taking back ko points. As soon as you add a stone somewhere (for instance by making a ko threat), superko no longer applies, it’s a different position.
If there is only one ko, you only need to include its status in the position’s description per AllanCrossman’s suggestion below.
The number of possible scores is limited by the size of the board. The number of available moves is also on the order of magnitude of the size of the board. The birthday paradox says that there is very likely to be a collision. Even more so since the scores aren’t evenly distributed.
It’s somewhat harder to estimate how often the best move will be one of the ties. Equally matched good players tend to end up with single digit (delta-)scores, which greatly reduces the range, and I have no particular reason to expect optimal play to differ in that respect. But if I invoke that statistic, then I also have to reduce the domain to however many moves said players would be unsure between, which I don’t know.
I don’t think you can use the birthday paradox here—since the expected values of go moves are best treated as being surreal numbers:
http://en.wikipedia.org/wiki/Surreal_number
Surreal numbers were actually originally developed to handle go move values:
http://senseis.xmp.net/?Infinitesimals
http://senseis.xmp.net/?GoInfinitesimals
But the only special value mentioned on those pages, = { 0 | 0 }, is not a surreal number. It’s a combinatorial game, and every surreal number is a combinatorial game, but 0 ≤ 0, making non-numeric.
Also, while values of fragments of Go games are best treated as combinatorial games, the final value of a Go game is always simply an integer (or even an element of the set {WIN, DRAW, LOSS}), and therefore so will the maximin.
The other infinitesimals listed on that page were: UP, DOWN, UPSTAR, DOWNSTAR, TINY, MINY.
The idea that you can subtract the maximin of a move with the maximin of passing to produce move values is unfortunately not correct, due to subtleties over who gets to play last.
Move values are surreal numbers. That isn’t an artefact designed to cope with partial games, it’s equally true of complete games.
The point is not trivial to understand—but it is relatively easy to see that the conclusion (that go move values are not integers) is correct. To do that, simply work through the whole board example given here:
http://groups.google.com/group/rec.games.go/msg/dc42f06aa5ad6bc1?hl=en&dmode=source
Who said anything about subtracting the value of passing? Passing is just another move, and has no inherent privilege over the other ~200 available moves. Ah, that’s where I was confused by your terminology: you speak of the value of a board state, which must account for what happens when either player plays on it, and passing doesn’t affect the board; whereas I was thinking of the value of a game state including whose turn it is, and passing transitions to a different game state. The former is more natural if you’re analysing partial games, and the latter is more natural if you’re brute-forcing maximin.
Auction Go is then a different game, some of whose moves are bidding in the auction rather than placing stones on the board. If you can bid fractional points, then the score is fractional, so move values can be too; and likewise for surreals or any other number system. The example you linked shows that changing the set of available bid-moves can change the outcome.
It appears that in the variation they’re using, which they call Auction Go, weird stuff occurs in which players can skip turns and stuff. Ordinary Go is the sort of game where turns simply alternate. I still think that game values in ordinary Go are always integers.
Auction go defines what “the value of a move” means. It is the smallest number of captures a perfect player would be prepared to accept as a payment for passing.
To calculate the value of a move, you have to compare moving with taking some kind of null action. That typically involves passing. Without passing (or something similar) there seems to be no way to measure the value of a move empirically.
This explains what I mean by “the value of a move”. However, I am no longer clear on what you mean by the term. You have some method of calculating move values which does not involve comparing to passing (or similar)? What do you mean by the term?
When I say “the value of a move”, I mean the score I’ll have if I make that move and everyone plays perfectly from then on.
That’s totally non-standard. Nobody else means that by the term. What if you are winning by 100 points? The value of filling a dame is then 100 points?!? If that is your definition, then no wonder we disagree.
At least it kind of makes sense if you subtract the value of passing, making the value of filling a dame one point.
Technically, superko deals with the whole history of the board. Repeated positions don’t only arise from single-stone captures—there are other ways of doing it—e.g. see:
http://senseis.xmp.net/?RoundRobinKo
Any earlier position could theoretically be recreated—if enough pieces are captured.