The board game Kalaha (or Kalah) is a perfect game for testing AI agents using the mini-max algorithm with or without alpha-beta pruning. The game rules are rather simple, it is possible to search for reasonably good moves in a couple of seconds, and still it requires very efficient implementation and pruning to create a good AI. The complete rules for the game can be read at Wikipedia.
This program consists of a Kalaha server (with a GUI) where you can connect clients using a client-server protocol. It also contains a number of clients; a human client (so you can play against your bad-ass AI), a random client (to test against), a Bad client (always makes the first possible move) and an empty AI client. I use Kalaha as an assignment for my students in an AI course where they are to implement their own mini-max based AI in the empty AI client class. Since these AI's have to optimize their performance to be able to search as deep as possible within a given time limit, students often want to use other programming languages which they believe is more powerful than Java. Therefore the program uses a client-server architecture where clients built in any programming language can be connected. To further motivate the students I often organize an informal Kalaha competition where their AI's compete against AI's by other students!
Note that the applet shown below is a modified version of the program without client/server communication and different GUI.