9 08 November 2009 02:53AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Sort By: Best

Comment author: 08 November 2009 01:01:20PM *  2 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?

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.

Comment author: 08 November 2009 01:59:25PM *  1 point [-]

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

Comment author: [deleted] 08 November 2009 02:46:27PM *  1 point [-]

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.

Comment author: 09 November 2009 05:39:47PM 0 points [-]

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:

Comment author: 10 November 2009 12:23:46AM *  1 point [-]

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.

Comment author: [deleted] 09 November 2009 07:25:43PM *  0 points [-]

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.

Comment author: 11 November 2009 09:59:29AM *  0 points [-]

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?

Comment author: [deleted] 11 November 2009 04:09:27PM 1 point [-]

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.

Comment author: 11 November 2009 06:04:18PM 0 points [-]

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.

Comment author: [deleted] 11 November 2009 07:53:02PM 0 points [-]

At least it kind of makes sense if you subtract the value of passing, making the value of filling a dame one point.