search

maxpumperla / deep_learning_and_the_game_of_go

Code and other material for the book "Deep Learning and the Game of Go"
https://www.manning.com/books/deep-learning-and-the-game-of-go
953 stars 387 forks source link

fix alpha beta to do more pruning #49

Closed namin closed 4 years ago

namin commented 4 years ago

Hello,

Thank you for a great book :)

I played with the alpha beta code, and I noticed that it's rather slow.

The issue turns out to be rather simple, after comparing with the canonical alpha beta algorithm:

Instead of using < one can use <= in the comparisons outcome... < best....

However for this to work with picking all best moves, one should change the top level to either not do any alpha beta optimizations or to restore the < behavior by being over cautious (e.g. substracting 1 on the best score).

The difference is very significant. You can play with the number of positions evaluated here:

In summary, for depth 3, we go from 12424 to 1713 positions evaluated for the black move after white move pawn e4.

This change also seems to speed up alpha_beta_go.py.

Note as well that I am happy to provide a chess hook in the style of the ttt directory for tic tac toe. Please let me know if you'd like that.

Thank you.

maxpumperla commented 4 years ago

@namin wow, that's phantastic... thanks for noticing! sometimes it can be a curse to work on a fast computer. :D

having a chess hook would be amazing, thank you! :heart: