Go is probably too complicated, and tic-tac-toe has some subtleties, but one thing that might be interesting and not too hard is to build a simple game, like nim, with *learning* capability. It's been a long while since I did this but I recall that it just involved making a tree structure to store possible moves, storing the results as a score, and then doing a tree traversal to see what gives you the highest or lowest "Score". Look up something called a "minmax" algorithm.
(although you'll find a bunch of people have done this particular one already)
The game of "mastermind" might also be a good balance of easy to program and interesting, although not so easy to do a tree for.
PS It's not perl but take a look at the Alice language from CMU. Makes it easy to do visuals to go with a game.
in reply to Re^2: [OT] Perl / Computer Science Science Fair Projects
in thread [OT] Perl / Computer Science Science Fair Projects