search

SanchoGGP / ggp-base

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

English Draughts oddity #227

Closed arr28 closed 9 years ago

arr28 commented 9 years ago

I think we made various questionable choices in this game of English Drafts, but ~40 moves before the end (move 111), we just gave away one of our pieces for no apparent reason.

Even if MCTS wasn't getting much signal, at least the piece heuristic should have prevented us from doing that.

SteveDraper commented 9 years ago

I actually think this might be explicable. If there is no capture within a couple of moves of that point the game terminates as a draw. If the game after the capture looked even a tiny tiny bit better than 50% we might have sacrificed to keep the game going. Logs of move values at that time should show if that is the case (everything would be at almost exactly 50%)...

On Thu, Apr 23, 2015 at 8:45 AM, Andrew Rose notifications@github.com wrote:

I think we made various questionable choices in this game of English Drafts http://www.ggp.org/view/tiltyard/matches/cf812506d81e55757df034a2243f407fe4b75d07/, but ~40 moves before the end (move 111), we just gave away one of our pieces for no apparent reason.

Even if MCTS wasn't getting much signal, at least the piece heuristic should have prevented us from doing that.

— Reply to this email directly or view it on GitHub https://github.com/SanchoGGP/ggp-base/issues/227.

arr28 commented 9 years ago

From a quick skim, I think these are the relevant logs...

03:59:35.937 - Starting turn 111
03:59:35.937 - MCTS iterations last turn = 179492
03:59:35.938 - Free all but rooted in state: ( ( true ( step 2 ) ), ( true ( lastToMove black ) ), ( true ( cell d 7 black king ) ), ( true ( cell a 2 black king ) ), ( true ( cell f 5 white king ) ), ( true ( cell g 8 white king ) ) )
03:59:36.245 - Freed 6% of allocated nodes (19246 of 319028)
03:59:36.245 - Root has 6 children, and is not complete
03:59:36.245 - Piece heuristic weight set to: 6
04:00:07.637 - Average fringe depth: 6.502765664447994
04:00:07.637 - Fringe depth variability: 1.8453033473763647
04:00:07.637 - Average branching factor: 3.1343165272218823
04:00:07.637 - Tree aspect ratio: 0.5875140502929058
04:00:07.637 - Move ( move f 5 g 6 ) scores 49.95 (selectionScore score 47.41, selection count 248968, ref 257699968125)
04:00:07.637 - Move ( move g 8 f 7 ) scores 48.53 (selectionScore score 42.35, selection count 2811, ref 223339891925)
04:00:07.637 - Move ( move f 5 e 6 ) scores 50.00 (selectionScore score 49.95, selection count 245967, ref 223340264590, complete [39])
04:00:07.637 - Move ( move g 8 h 7 ) scores 49.17 (selectionScore score 45.55, selection count 9818, ref 266289873985)
04:00:07.637 - Move ( move f 5 e 4 ) scores 47.18 (selectionScore score 38.00, selection count 1389, ref 188979562040)
04:00:07.637 - Move ( move f 5 g 4 ) scores 48.63 (selectionScore score 45.08, selection count 10095, ref 214749223612)
04:00:07.637 - Most likely path: ( move f 5 e 6 ), ( move g 8 f 7 ), ( move f 5 e 6 ) | ( move a 2 b 1 ) | ( move d 5 c 6 ), ( move b 1 c 2 ) | ( move c 6 d 7 ), ( move c 2 d 1 ) | ( move d 7 c 8 ), ( move d 1 c 2 ) | ( move c 8 d 7 ), ( move c 2 d 1 ) | ( move d 7 c 8 ), ( move d 1 c 2 ) | ( move c 8 d 7 ), ( move c 2 d 1 ) | ( move d 7 c 8 ), ( move d 1 c 2 ) | ( move c 8 d 7 ), ( move c 2 d 1 ) | ( move d 7 c 8 ), ( move d 1 c 2 ) | ( move c 8 d 7 ), 
04:00:07.637 - Num nodes in use: 310059
04:00:07.637 - Num true rollouts added: 7133584
04:00:07.637 - Num terminal nodes revisited: 143400
04:00:07.637 - Num incomplete nodes: 0
04:00:07.637 - Num completely explored branches: 175390
04:00:07.637 - Current observed rollout score range: [0, 100]
04:00:07.637 - Playing move: ( move f 5 e 6 )
04:00:11.009 - Moves played for turn 111: [( move f 5 e 6 ), noop]
04:00:11.009 - Non-null move last turn was: ( move f 5 e 6 )
arr28 commented 9 years ago

So, we think that reducing ourselves to 1K is a forced draw and that everything else is (slightly) worse.

However, I'm highly dubious that reducing ourselves to a 2 vs 1 position is actually a forced draw. It's my understanding that, in almost all situations, 2K vs 1K is a win for the 2K player. I thought that the only occasion where the 1K could recover a draw is a very specific situation where the 2K are stuck in the corner on the single diagonal.

However, I think you imply that there's some move limit that we might reach first. The logs would imply that it's at least 39 moves away from the capture though and I reckon black's forced win can't be much deeper than that.

arr28 commented 9 years ago

Ah, you only get 20 moves (10 each) without a capture before the game ends. So that "complete in 39" must involve taking one of the opponent pieces in the middle of the sequence. I can well believe that there isn't a forced win in 20 moves (and then it's 1K vs 1K so very likely to be a draw).