Minimax: how can I implement it in Python?

Question

As long as I've been a programmer I still have a very elementary level education in algorithms (because I'm self-taught). Perhaps there is a good beginner book on them that you could suggest in your answer.

Answer 1

As a general note, Introduction to Algorithms. That book will get you through pretty much everything you need to know about general algorithms.

Edit:

As AndrewF mentioned, it doesn't actually contain minimax specifically, but it's still a very good resource for learning to understand and implement algorithms.

Answer 2

Look at the wikipedia article on Negamax: http://en.wikipedia.org/wiki/Negamax. It's a slight simplification of minimax that's easier to implement. There's pseudocode on that page.

Answer 3

There is an implementation of minimax as part of an othello game here (and for browsers here). Stepping through this with a debugger and/or through use of logging statements may supplement theoretical descriptions of the algorithm.

This visualization applet may also help.

At each stage the player will choose the move which is best for himself. What's best for one player will be worst for the other player. So at one stage the game state with the minimum score will be chosen, and at the next stage the game state available with the maximum score will be chosen, etc.