Recently the Advanced Placement Computer Science mailing list had an exchange looking for ideas/suggestions for games that students could program artificial intelligence routines for. A number of suggestions came out - Connect Four, Abalone, Kalah and 3D Tic Tac Toe for example. There was some discussion that regular tic tac toe was too easy. Another popular suggestion was Reversi, also known as Othello. These are all interesting suggestions but I have a fond place in my heart for Reversi. Reversi was the first serious game that I tried to write an AI for. That game taught me a lot. It taught me some about AI but what it really taught me about was the need to understand the problem.
This project was a long time ago and I no longer have the code. I remember a lot of the algorithms though. How do I remember the algorithms after so long? Basically because I tired to program the computer to play the way I play. The good news is that I pretty much succeeded in getting the computer to play as well as I do. The bad news is that I don’t actually play he game that well. And here is the root of the difficulty of programming artificial intelligence – you have have really understand the game and how who win at it. You have to know what perfect play is (or close to it) and then you have to be able to tell the computer how to replicate that sort of play.
With Reversi the simplest and easiest strategy is to search the board for the move that turns over the most of you opponents pieces. Like most simple and obvious solutions for complex problems this one is horribly flawed. A good player will almost always beat someone using that strategy. The next step then is to learn about moves that are valuable for other reasons such as edges which can give you more control of the board and corners which are still more powerful. It turns out that those are not absolute values though. They depend on circumstances on the board. This means that the rules for play that one creates have to have exceptions and times when “it depends” before making that move. This is common in games.
Less widely known, or imagined by students, is that this sort of thing happens in business applications as well. I once had to write some code to determine cutting instructions for orders of fabric. It turns out the the rules for this are extremely complex. If one can’t cut all the fabric from one roll the next length has to come from the same lot. And the determination of how much fabric to cut from each roll depends on some rules about length of scrap on the piece used and on the piece left behind. And more. It took me several weeks of discussions with people who made these decisions manually (and expertly) in order to understand the process well enough to have the computer duplicate their thinking. Understanding the problem was the single most important piece of the process. The best programming in the world can’t solve a problem they don’t understand.
Returning to the use of AI in games as projects. One of the fun things to do is to have individuals or teams work on their own AIs for a game and then have the various programs “play” against each other to see who has the best algorithms. Students usually love the competition and it gives them some incentive to work hard on it. The big caveat of course is that there are algorithms and code samples out of the Internet from many of these games. When evaluating these projects an instructor has to look closely to make sure the code is original. Personally I have less of an issue with students implementing an algorithm they find as opposed to just plugging in the code. In most cases though these are larger more important projects that, in high schools at least, they are probably worth big enough grades that the instructor should think about interviewing the teams to make sure they can explain exactly what is going on.
> ...had an exchange looking for ideas/suggestions for games that students could program artificial indolence routines for...
That's got to be one of the best auto correct errors I've ever seen in my life!!
Spell checkers are a blessing and a curse. :-) I have corrected it in the text so we can let people wonder where the error was. Thanks for catching it.
My experiments actually went into a totally different direction. I used an evolutionary algorithm and let the AI figure everything out itself. It could even adapt to rule changes.
'...and then have the various programs “play” against each other'
For the ancient game of go, there is a server where AIs compete with each other: cgos.boardspace.net/.../standings.html
PS There is a Wiki to help you get started if you fancy writing an AI (aka "engine") to play on the CompterGo Server here: computergo.wikispaces.com
Look into Microsoft Solver foundation and optimization algorithms to solve cut stock problems such as rolls or fabric, paper, lumber, or whatever.
the problem with using reversi is that I'm willing to bet most of your high school students, and many of the college students have never played nor heard of Othello/Reversi (I'm guessing this is mainly aimed at HS, since you said it's the AP mailing list).
Heck, I'm 25, and while I've heard of it, I've never played it.
When I was in AP courses (C++ in 2003, Java in 2004) I believe our "big" game/ai project was 3D tic tac toe and "Battleship". I believe we also programmed a fish tank simulator, but I don't remember how successful those were.
Good AI is an integral part of most games these days. I think the difference between good AI and mediocre AI is the number of layers of adaptability and pattern recognition. Ie, 1. can the game notice and recognize patterns of player behavior? 2. can the game recognize that the player has adapted to the game's adaptations from step 1? These guys do good work in this area: http://www.gameshastra.com