Reducing search cost

[depthfirst]

Running time is an issue, obviously. Example below is not bad at all, but easy to try different techniques on before a longer running test.

Example (dev/18k/3209): start (7x9): w=0, b=0, nw=10, nb=8 White to Live - black=True, isBtL=True SOLUTIONS: B(1,5): w=0, b=0, sw=0, sb=0, nw=10, nb=9 W(0,4): w=0, b=0, sw=0, sb=0, nw=11, nb=9 B (3,5): w=0, b=0, sw=0, sb=0, nw=11, nb=10

GOLD: B(0,7): w=0, b=0, sw=0, sb=0, nw=10, nb=9 0.648 (198.0 seconds). W(1,4): w=0, b=0, sw=0, sb=0, nw=11, nb=9 0.407 (187.4 seconds). B(1,1): w=0, b=0, sw=0, sb=0, nw=11, nb=10 0.615 (198.6 seconds). W(4,3): w=0, b=0, sw=0, sb=0, nw=12, nb=10 0.395 (217.5 seconds). B(5,6): w=0, b=0, sw=0, sb=0, nw=12, nb=11 0.582 (227.2 seconds). W(3,5): w=0, b=0, sw=0, sb=0, nw=13, nb=11 0.407 (248.6 seconds). B(4,7): w=0, b=0, sw=0, sb=0, nw=13, nb=12 0.571 (251.3 seconds). 'Too many moves, you lose!!'

[depthfirst]

Switched to DFS (from BFS) - as expected, no change in performance in this case, since we build the whole tree. Hashing the board was horrible, guess we'll need Zobrist hashing as Zach suggested. Here's a cost breakdown of the first move:

Found 45 valid moves in 0.1 seconds. Added 83,512 nodes to search tree in 184.6 seconds (running terminal test for each) Move decided in 7.3 seconds. (following feature extraction and classification for all 45 first moves) B(0,7): w=0, b=0, sw=0, sb=0, nw=10, nb=9 0.648 (192.0 seconds).

[depthfirst]

Of course, just building the tree even without the terminal test or feature extraction has a cost of its own:

Added 87122 nodes to search tree in 25.3 seconds

[MrTyton]

Holy shit that's a lot of nodes.

On Thu, Dec 11, 2014 at 12:44 AM, John Blackmore notifications@github.com wrote:

Of course, just building the tree even without the terminal test or feature extraction has a cost of its own:

Added 87122 nodes to search tree in 25.3 seconds

— Reply to this email directly or view it on GitHub https://github.com/RU-CS530-Go-Team/GoLD/issues/23#issuecomment-66575996 .

[depthfirst]

45x44x43=85,140, so there have to be duplicates, which follows what I was saying earlier. . Anyway, feature extraction only took 7.3 seconds (for 45 nodes). Would be nice to cut down, but if life.py runs faster, it'll have a much larger impact.

[MrTyton]

life.py is definitely running faster. On full boards it can still be a bit slow but I'm pretty sure that it's still doing it faster. Remember that it's an O(n^2) operation each time (big more expensive but that's big O), and I can't really reduce it past that because I have to go through the whole board at least once.

Only found 3 problems, where it misclassified something as unconditional life when it wasn't, in all of the train data. I think that's acceptable. Tomorrow I might go for some more performance tweaks in life.py, without changing the overall algorithm. Not entirely sure how to fix those last 3 problems though, but it's a very very specific occurrence that doesn't happen often.

On Thu, Dec 11, 2014 at 1:25 AM, John Blackmore notifications@github.com wrote:

45x44x43=85,140, so there have to be duplicates, which follows what I was saying earlier. . Anyway, feature extraction only took 7.3 seconds (for 45 nodes). Would be nice to cut down, but if life.py runs faster, it'll have a much larger impact.

— Reply to this email directly or view it on GitHub https://github.com/RU-CS530-Go-Team/GoLD/issues/23#issuecomment-66578362 .

[depthfirst]

A colleague offered an interesting suggestion. Rather than search the whole tree for terminal states, then evaluate all the first moves if none found, do the opposite, going back to our beam search. Evaluate the first moves, then search the top k nodes for terminal states. The tradeoff of course is that we may not find terminal states that exist, but we would have more control of our search space. Worth a try?

[MrTyton]

Yeah probably.

On Thu, Dec 11, 2014 at 6:05 PM, John Blackmore notifications@github.com wrote:

A colleague offered an interesting suggestion. Rather than search the whole tree for terminal states, then evaluate all the first moves if none found, do the opposite, going back to our beam search. Evaluate the first moves, then search the top k nodes for terminal states. The tradeoff of course is that we may not find terminal states that exist, but we would have more control of our search space. Worth a try?

— Reply to this email directly or view it on GitHub https://github.com/RU-CS530-Go-Team/GoLD/issues/23#issuecomment-66705869 .

[depthfirst]

Making progress... searching faster, pruning more and winning.

Found 45 valid moves. Created 45 children in 0.0 seconds. Evaluating 45 moves b(0,4) w(1,5): White evades! b(1,5) w(0,4): White evades! Extended tree by 83512 nodes in 107.0 seconds. B(4,0): w=0, b=0, sw=0, sb=0, nw=10, nb=9 0.676 (114.9 seconds, 1936 nodes). W(1,8): w=0, b=0, sw=0, sb=0, nw=11, nb=9 0.286 (109.4 seconds, 1850 nodes). B(0,4): w=0, b=0, sw=0, sb=0, nw=11, nb=10 5.000 (105.4 seconds, 125 nodes). W(0,0): w=0, b=0, sw=0, sb=0, nw=12, nb=10 5.000 (2.3 seconds, 2 nodes). B(1,5): w=0, b=2, sw=0, sb=0, nw=12, nb=11 5.000 (0.0 seconds, 1 nodes). You Win!!! Black has 2 groups that are unconditionally alive!