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.
I hope everyone (US anyway) had a great Thanksgiving last week. For me it was a good time with fun, food and family. We had a great time with my new Kinect sensor with Xbox 360. A great way to work off Thanksgiving dinner. With much of the week off (hooray for a 5 day weekend) I didn’t Tweet a whole lot. Even still I have a few good links to share. I hope you find something you can use here.
Have you seen INTERRoBang yet? “The socially-networked, mission-based, problem-solving game in partnership with the Smithsonian, Learn and Serve, sponsored by Microsoft” On the web at http://playinterrobang.com/ and you can follow them on Twitter at @playinterrobang
We are closing in on Computer Science Education week (Dec. 5-11th) and CSTA is out with a number of Audio and Video Announcements that you can use. The ones I looked at really looked great. Use them to help build interest in and knowledge of computer science.
A reminder that you can provide a huge amount of professional software for your high school students through the DreamSpark program. Gautam explains "How can High School Teachers provide students with DreamSpark Software" on his blog.
Hélène Martin had a pair of great posts last week.
Hélène is scary smart and her posts always make me think. I highly recommend her blog in general and these posts in particular.
Speaking of other blogs, there is a new list of Top 50 Computer Science Bloggers I'm a sucker for lists that list my blog but this one has a lot of really good looking blogs listed. Some of what I knew about already but a good many that are new to me. You may find something useful there yourself. The same site has a post on Must-See TED Speeches for Computer Scientists that looks interesting.
When something I think about a good deal turns up in two or more blogs written by other people my feeling is that this is a sign that I should blog about it. Blogging helps me get my thoughts in order. So when Mark Guzdial writes “Computer Science as a Path to Computer Application Efficacy” which discusses if learning computer science translates to people being better at using computer applications and CSTA Vice President Steve Cooper, writing in the CSTA blog, writes “Program or be Programmed” which talks about making computer science learning relevant and helpful for other subjects I know I have a topic.
My friend David Klappholz tells me that there is a lot of research that shows that various subjects have far less transference than we in education would like to think. For example the theory that learning Latin helps learn English turns out to be pretty much a myth. Learning problems solving in math tends not to transfer to problem solving in other subjects as much as we wish it might. Now Dave is a very smart guy and has done a ton more research than I have ever or will ever do in my life. So perhaps I should assume that there is not much transference between computer science and anything else. But I’m stubborn. And like most people I tend to believe what I want to believe. So here is what I think about learning computer science.
I think it does transfer to learning and using computer software. Now that is a big thing because we all use software more and more. I talked to a former student of mine some time ago. He’s a blacksmith now. Yeah, hammer, hot iron and an anvil sort of work. But he uses CAD software to design a lot of his custom iron work. He told me that he feels that having had some computer science helps him understand new CAD software better. Mark Guzdial’s post (address) contains similar talk from students. Now antidotal evidence is not proof but it is enough to start some working theories.
My first thought was that learning computer science helps understand how computers and computing works and so helps understand the limitations and abilities of software. I think it is a probability. But I wonder if another piece is that learning computer science helps one understand how programmers think. A lot of programmers think differently. From each other and from the rest of society. Some of that is personality and some of that is dealing with the constraints of the hardware and software. Some of it may also be the culture of thinking that CS has developed and which is perpetuated by how we teach computer science. But for what ever reasoning for these thought patterns they shape how software works and so understanding the mindset may help. It’s a theory. Feel free to shoot it full of holes.
On a more mundane but main stream way of thinking I believe that using many applications is easier if one understands computer science concepts. Using a database tool is easier if one understands Boolean searches for example. Even using an internet search engine (I use Bing to do my googling ) is better if you know how to use Boolean commands. Using a spreadsheet is better if you have a grasp of conditionals and how computers like to see formulas expressed. There is also a matter of understanding ones results in the context of how literal computers and computer software can be. And probably more as well.
Maybe learning computational thinking for/with computer science doesn’t transfer to more general problems solving. But maybe it does. My gut tells me that if we teach it correctly, not always easy, it will transfer. I think this because computer science is, to me, a lot of understanding thought, learning, and thinking. Not just how we do it or even just how the machine does it but how the two work together. Or don’t as the case may be. I think that computer science expands how we think. And wishful thinking or not I believe that this is something that transfers to other areas. Now go ahead, confuse the issue with facts.
Oh BTW also closely related to this post of mine is Mark Guzdial’s post “Computing Education Research vs Real Education Research”