I've always wanted to build a chess AI that could beat me at the game. Last term my friends and I would play chess, and I would almost always lose. Fed up, I challenged them to a chess AI contest, where we would build our own bots and have them compete (we are programmers after all). I ended up being the only one to actually write an AI.
I started by watching this lecture and building a simple tic-tac-toe program using the minimax algorithm. I added alpha-beta pruning as an optimization, and refactored the code to make the AI logic separate from the game-specific logic. I applied the refactored code to Connect-Four as well. Finally, I implemented chess. You only need to provide 2 functions to apply this AI to a new game: a function which inputs a board and outputs a list of boards that will result form a single move, and an evaluation function which maps a board to an integer value representing the likelihood that player 1 will win.
The move generator function is fairly simple for chess: you have to iterate over all the pieces for the current player and translate them in every possible way. The board evaluation function is more interesting: I value the board based on the total value of the material (queen is 9 points, pawns are 1 point, rook is 5 points, etc), the number of moves the other player can make (we want the other player to be as immobile as possible) and the domination (how close are the player's pawns to the opposite side). There are more sophisticated evaluation functions out there, but this was good enough to beat me and my friends.
I give the AI 7 seconds per turn, which allows it to search the tree at a depth of 5-10. I used Iterative Deepening to force the search into a time constraint. The deeper the search is able to go, the more accurate the move will be. Given 7 seconds on a micro EC2 instance, the AI is able to defeat the average chess player (myself included). If I were to optimize memory allocation, use multi-threading, and use a larger instance, I could achieve a deeper search.
I deployed the chess AI as a backend service running on an EC2 micro instance. You can play it here.