Board games
One search engine, three games. Set it to very hard and it looks eight moves ahead — you will notice.
One search engine, three games. Set it to very hard and it looks eight moves ahead — you will notice.
All three games share one brain, because all three are the same kind of problem.
Checkers, Reversi and Four in a Row are perfect-information games: nothing is hidden, there's no luck, and the whole future of the game is in front of you. That means the same algorithm plays all three — minimax with alpha-beta pruning. It looks at every move it could make, every reply you could make, every answer to that, and so on to the depth you've selected, assuming throughout that you'll play as well as it would.
The games differ only in what a position is worth. In Four in a Row it counts open lines of two and three, and prizes the centre column. In Reversi it prizes corners enormously, punishes the squares next to them, and counts how many moves each side has left — because taking away your options is worth more than taking your discs. In Checkers it counts material, values kings, and pushes men towards the crowning row.
Set the level to easy and it looks two moves ahead, which is beatable. Set it to very hard and it looks eight, which mostly isn't.