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.
No comments:
Post a Comment