Tic-tac-toe or Nim or another simple game, but rather than writing a program that plays it perfectly, write a program that learns from experience and let two programs "play" against another, to build up their databases of good and bad moves. How many games does it take before you cannot beat it anymore?
in reply to [OT] Perl / Computer Science Science Fair Projects
A program should be light and agile, its subroutines connected like a string of pearls. The spirit and intent of the program should be retained throughout. There should be neither too little or too much, neither needless loops nor useless variables, neither lack of structure nor overwhelming rigidity." - The Tao of Programming, 4.1 - Geoffrey James