The encryption idea was my favorite, because based on how fast the base part of the project got done there is a lot of room to spend time making it smarter and faster.

Good points about tic-tac-toe, which was actually the game I had in my head while writing. My worry, I think, might be the difficulty convincing an older science teacher with limited domain knowledge that the problem is hard enough for a science fair project.

My sister mentioned the game of go, because she plays, but I don't think we could come up with an appropriate problem. Even small problems, like for example life and death of stones, are really hard. Limiting the game to a board small enough to be searched, you get into gross ruleset specific distinctions.