Search code examples
algorithmminimaxalpha-beta-pruning

Whats the difference between scout algorithm and minimax with alpha beta prunning?


I am trying to implement a scout algorithm as implementation for an Othello game, I have already implemented minimax (and negamax) using alpha beta prunning, and now I can't see the difference between the two algorithms and there is little help about it online. I don't really want pseudocode, just help understanding the idea behind the scout approach and how is that different from minimax with alpha beta.


Solution

  • The idea behind NegaScout is that if you have good move ordering you can search the first move normally and then simply scout the rest of your moves. You scout by searching with a null window, and you're effectively asking: "Is the alpha I got from the first move the best I can do?". The null window search will cause more cutoffs that normal and you should save some time, but if it fails you got nothing from the search and you have to restart with the normal alpha and beta bounds. source

    I don't know much about Othello but it seems like it can be difficult to get the ordering right. If so you won't get much out of NegaScout. Also NegaScout can be tricky to implement and verify.