Hoping for lots of discussion after Friday

[Fritzlein]

The difference in endgame moves after separation is roughly equal to K1 * (player 1 fillable squares - player 2 fillable squares) + K2 * (player 1 sum of edges - player 2 sum of edges) + K3 * (irrelevant factor). [...] I found K1 to be about 0.050, K2 about 0.150, and K3 less than 0.009. Hence I consider the third factor pretty much irrelevant.

Wow, thanks for sharing this. Your earlier brief summary made me wonder how you topped the standings using only ideas that had been openly discussed. Was your implementation simply blindingly fast? No, you (also?) had a better eval! Like you I'm surprised at the empirical importance of edges rather than vertexes, but hey, whatever works. Those factors penalize holes in the map that our eval didn't penalize at all, and holes are what always stop us from reaching the upper bound. Great idea to fit the parameters to actual game results.

On a totally unrelated note, I'm rooting for you because I think it would be hilarious if a Yahoo won the Google AI challenge.

[psb217]

Actually you'd need to multiply the edges by 3, not by 0.25... The edges totally dominate the heuristic value. Dunno why, but it seems to work. It definitely keeps it from cluttering up its own space though.

What I meant was that the score for each player was: p_score = p_edge_count + 0.25 * p_vert_count

My verbal description was somewhat ambiguous. The overall score was me_score - them_score. Thus, I was putting four times the weight on edge count as on vertex count. Your weights indicate three times the weight on edge count as on vertex count, i.e. 0.150 vs 0.05.

[a1k0n]

Thinking about it a bit more, it's totally logical why the numbers came out that way. Each edge gets counted twice (if A has an edge to B, then I count that edge both for A's square and for B's square.) The average number of edges per node is probably slightly above 3. 2*3*.150 + 0.050 is 0.950, or close to one "endgame node" per "midgame territory node", so to speak, if the endgame is the point after separation. Least squares estimation just weighted it that way and it would probably be equally valid to weigh it differently. So it was a lot of work to get a simple result, which is one reason I didn't really say anything about it sooner. I guess at least thinking about the issue was important.

I probably could have done some more fancy inference on nodes which are corners, passages, etc, and gotten a better heuristic. But I honestly didn't think of it until luv2run mentioned it today. I was more concerned with figuring out which areas are useful to the bot and which need to be ignored because of narrow passages preventing a return to the area.

[Fritzlein]

Thinking about it a bit more, it's totally logical why the numbers came out that way. Each edge gets counted twice (if A has an edge to B, then I count that edge both for A's square and for B's square.) The average number of edges per node is probably slightly above 3. 2*3*.150 + 0.050 is 0.950, or close to one "endgame node" per "midgame territory node", so to speak, if the endgame is the point after separation. Least squares estimation just weighted it that way and it would probably be equally valid to weigh it differently.

I think the math is off there, because saying that the average edges per node is a little above three is already double-counting them. When you multiply by two, you quadruple count them. In fact the average edges per node will be closer to 1.5.

But regardless, just because there are different weights that add up to one doesn't mean they are all equally valid. Consider the endgame below:

Code: Select all

##########
#       ##
#       ##
#       ##
#   1   ##
##########
#    2   #
#        #
#   ###  #
#        #
##########


I count that Player 1 has 28 vertices and 45 edges, whereas Player 2 has 29 vertices and 42 edges. If you like territory more you think Player 2 is winning, but if you like neighbors more you think Player 1 is winning. (Note that building a "tree of chambers" doesn't provide discrimination, because each player has a single 2-connected component. Note further that the "checkerboard" upper bound doesn't discriminate because it thinks both players can get all their remaining territory.)

If your preference for "clean" territory over "ragged" territory wasn't responsible for your dominating performance, then what was?