SanchoGGP / ggp-base

The General Game Playing Base Package
8 stars 4 forks source link

Investigate Kalaha 6x2x4 loss #224

Open arr28 opened 9 years ago

arr28 commented 9 years ago

We lost this match of Kalaha 6x2x4. Local logs (not uploaded because they're too large) showed an expected score of ~80 up to about half way through the game. Then came a "surprising move" (virtually all of the node pool freed, score immediately drops to 50). A little while later, our expected score dropped to 0 and remained there.

I note that GreenShell's logs are the inverse of ours. Its score decreased down to <20 then suddenly jumped up 50. So the surprising move surprised both of us.

arr28 commented 9 years ago

Looking through the logs...

arr28 commented 9 years ago

This game must be a really good exercise of the hyper-edge code. I wonder if that's where the problems are here.

The whole game only consisted of 46 "pick" moves and from the point where I began the commentary, it was only 26 moves long. Maximum branching factor was 6 and average branching factor was probably more like 4. That's still 4x1015 moves though.

Thinking about this game, it's probably a real shocker for MCTS. Random moves are a really bad approximation to reality. Until there is significant branch completion happening, the values coming back from MCTS must be extremely noisy.

I suspect there's no "bug" here and that it's just a game that sucks with MCTS. Re-tagging accordingly.

SteveDraper commented 9 years ago

This game displays a similar issue: http://www.ggp.org/view/tiltyard/matches/31da6caf28a7b3ed393e864747c553b6758d1320/

Around turn 14 or so, in a forced move sequence, the estimated score drops rapidly even though the tree is utterly unbranching in this time.

SteveDraper commented 9 years ago

Interestingly this seems to happen about when the node table fills up

arr28 commented 9 years ago

Consider whether this is also related to #229 where there was suddenly a huge drop (to 0 in this case) in D&B. These are both games with a considerable "1 player retains control for a while" element so consider issues with hyper-edges.