http://qs1969.pair.com?node_id=709786


in reply to [OT] Perl / Computer Science Science Fair Projects

Something with board games and AI. Perfect play with a trivial game seems too modest a project

I disagree. For a 9th grade that's not so very easy. For example Tic-tac-toe has 0.3M possible game plays, so one could implement searching in the tree, and then using symmetry to reduce the the tress size. You have to know how to backtrack, build and traverse a tree. That might seem trivial to us, but isn't for somebody who has never done it before.

Another game that might be interesting and not too hard if done imperfectly is Connect Four, but I wouldn't inflect that on a 9th grade.

Encryption. Probably something involving frequency analysis to break substitution ciphers.

I think that's quite a nice one, because you can get a result rather quickly, but still can optimize quite much (for example you can use a dictionary, digraph and trigraph tables that you build from the dictionary etc, but you already get some intermediate results for longer encrypted texts by using very simple approaches).

Replies are listed 'Best First'.
Re^2: [OT] Perl / Computer Science Science Fair Projects
by MidLifeXis (Monsignor) on Sep 08, 2008 at 15:56 UTC

    I wish I could ++ this a few times.

    The computer science club at my college used to (perhaps still does) host a programming contest for high school students. While the participants were under a more compressed time frame, the assumption that we made for the easiest program was if/then/else and a loop construct of some sort. More advanced problems included nested control structures, switch statements, text processing (think split and join), and other problems that are easily programmed multiple times a day by anyone who does a modest amount of programming.

    Remember that this should stretch the capabilities of the student, not stress them to the point of breaking :)

    --MidLifeXis

      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.
Re^2: [OT] Perl / Computer Science Science Fair Projects
by amarquis (Curate) on Sep 08, 2008 at 15:54 UTC

    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.

      Depending on how your sister implements it, the project could teach basic game theory, recursion, a-b pruning, and other advanced (for high school, and somewhat for early college) topics. Show the teacher some of the classic literature, and how even something as "simple" as the Missionaries and cannibals problem can be mapped into the same problem space.

      Perhaps the game is not the way to present it to the teacher, but the way the game is solved.

      --MidLifeXis

      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.

      There are two problems in Go that I would think might be appropriate (assuming that 9th grade == somewhere around about age 14).

      The first, and the easiest to demonstrate because it's quickest, would be figuring out whether a move results in a group that is entirely surrounded and can be removed from the board.

      The second, which builds on that, would be to implement a board on which two people can play, with the computer removing prisoners during play as above, but also spotting and not allowing other illegal moves such as suicide or repetition. Don't worry about the ruleset distinctions - just pick one and go with it.