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.

I think that shouldn't be a blocker. People can be dealt with, if you know how ;-)

Some people are easily impressed by numbers. For example the game could have a small counter telling you that there are $n possible game plays left, and $n starts at 300k. That demonstrates that the program does really much work.

I assume that she has to write some kind of description, and if that nicely illustrates the search trees, that could convince other teachers.

Again others are impressed by everything that computers do, those should be the easiest to convince.