Additional profile information on Alfred Thompson at Google+
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.
Last summer I helped present two talks at the CSTA CS & IT Symposium. In both cases I had small rolls with Pat Philips doing almost all of the talking on the talk about the Expression Web course. Steve Scanlan, an wonderful classroom teacher, did most of the talking after my introduction of game development on the XNA talk. The recordings of both of these talks are available through the CSTA web site. If you are thinking at all about adopting a game development computer science course or a new web development course you will find these talks interesting.
Computer Science, Game Development and the XNA Game Studio Platform Presented by Alfred Thompson & Steve Scanlan This presentation talks about creating and implementing a high school game development curriculum using the (free) XNA Game Studio. We present the reasoning behind this type of course, show screenshots and a video introduction to student projects, as well as show examples of the sort of code students can create. We also talk about how freely available curriculum has been used and modified with real students. We present a collection of helpful resources including websites, tutorials and videos from Microsoft and independent web sites.
Download presentation as PDF (2 zipped files) View streaming video of session
Web Design and Development—A Key to a Growing Program Presented by Pat Phillips & Alfred Thompson It's quick and easy for students to create interactive websites using the professional Web design software from Microsoft—Expression Studio 3. Learn how your secondary schools can receive Expression Studio at no cost! Explore the free teaching and learning resources that will enable you to add Web design to your students' toolbox of communication tools and explore deeper Web development techniques. The free curriculum materials range from 2-hour tutorials, to 2-week multi-disciplinary units, to a full semester of comprehensive Web design concepts. All of the materials were created by teachers and tested by students. Students can install the software free of charge on their personal computer making this a valuable software option for many schools challenged with providing professional design and developer software to students.
Download presentation as PDF View streaming video of session
Graphics can be a lot of fun for students. Well honestly they are fun for a lot of adults. Recently I read a blog post by Cate Huston (Experimenting with a Visual, Activity-Based Curriculum) about some totally visual, graphical project based learning she was working on. Leading off was an image that brought back lots of fond memories for me. You see back in the old days before graphical capable monitors our best, often only, way to do colorful graphics was via dumb plotters. It was with one of those that I discovered computer graphics and with that the interested things one could do with straight lines. For years (dare I suggest decades) my graphical version of “Hello World” has looked something like this.
Don’t you just love the patterns? OK may be it is just me. The code for this example is in Small Basic BTW and looks like this:
Pretty simple. The first version of that I ever wrote was in FORTRAN and I’ve lost count of how many times I have written it since. It’s a simple fun example and it makes a good demonstration of simple looping. But you can get a lot more complicated. You can also have it draw in all four corners like the sample on Cate’s blog post.
One of my favorite programs from college was a program that drew shapes based on how many sides I asked for. OK that was too simple so I then had the program rotate the shape and shrink it until small and then increase the size until full sized again.What did you get? Something like this.
Those are obviously three and seven sided figures. (That program is written in Visual Basic FWIW) There are patterns in both that I never anticipated before I had the computer draw them for the first time. They are caused by moiré patterns BTW. A two sided shape really surprised me but I leave drawing that to the student. In fact it was the surprises that made this program so much fun for me.
Several of my friends experimented with graphing different equations while we were in college. Some of them created some very interesting designs that way. I think when we think graphing equations we look at things that are linear or very simple but a real mathematician can, I am sure, find some equations that are a lot more visually interesting and dare I suggest surprising to students. It seems to me that a bit of a surprise can be a good thing. We need more of it!