Maybe implement Minimax [1] in your favorite language and apply it to a simple game like tic-tac-toe.

[1]: http://en.wikipedia.org/wiki/Minimax