Computer Science Teacher
Computer Science Teacher - Thoughts and Information from Alfred Thompson

November, 2010

  • Computer Science Teacher - Thoughts and Information from Alfred Thompson

    Artificial Intelligence and Game Programming


    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.

  • Computer Science Teacher - Thoughts and Information from Alfred Thompson

    Teaching real-world programming


    The title of this post is borrowed from an article at the MIT (original article at Teaching real-world programming) about a programming course at MIT that uses professional software developers to help mentor students. The professionals perform what amounts to a code review of student code. The review is not part of the grading process but part of the learning experience. I love this idea. For me learning rather than grading is what a good educational experience should be all about.

    The professionals volunteer and since the Cambridge.Boston area is a hub of hi tech companies and working with MIT is a high prestige sort of thing they don’t lack for volunteers. So this program might not work everywhere. But I wonder if it could be tried on smaller scales at least at other places – including in high schools. I can see it being very helpful. The article highlights a couple of things I learned while I was teaching. I hear similar things from other teachers. For example:

    Harried professors and teaching assistants can look over the students’ code and flag a few common and obvious errors, but they rarely have the time coach the students on writing clear and concise code.

    Students often don’t care how clear or concise their code it. They are just in a hurry to get things done and in for a grade. Learning to take their code to the next level (clear and concise) takes a bit more work. Friends of mine have talked about coding apprenticeships which beginners learn by working side by side with “master programmers.” This is often what happens when people leave school and take their first software development job. It would be nice if they could get some of that in school though.

    Also programming is really more like a craft or even an art than a true engineering science. I know that is a matter of contention but while I would like it to be real engineering I don’t think we are quite there yet. And so programmers need to developer a style. As it says in the article:

    In many computer-science classes, Amarasinghe says, professors trying to preserve intelligibility will insist on a particular style of coding, which may not be natural for some students and, he says, can actually lead to bad code. “The way we look at programming, it’s like writing an English paper,” he says. “If you are in English class, there’s no set way of writing.” What’s important is that a programmer’s style be consistent, not that it slavishly ape some model.

    A mentoring process with an experienced professional can help students develop that style while also developing a clarity of thought and of coding that will serve them well.

    How might this work in a high school? There are probably several ways but I wonder if a small number of volunteers could dedicate a day where they code review individual or small team projects. Perhaps in the middle of the semester or near the semester break of a year long course. Ideally the project would be reasonably complex – not too long but long enough for personality and habits to be visible. The reviewers would get advanced copies of the code and so come with questions. I see this working better by starting with questions “Why did you do this?” “What does this do?” “What other ways did you consider?” and on and on. Spend an hour or so going line by line perhaps. Seems like it might be useful.

    I’ve quickly reviewed student code on visits to schools in the past BTW. Generally I only have time to scan the code and ask a few questions. What is amazing is how often I ask or tell the students things they have heard from their teacher. Students are surprised when this happens though of course they shouldn’t be. I like to think that these outside comments help build teacher credibility as well as reinforcing learning. Doing this on a larger more formal set up seems like a valuable effort.

    The hard part I admit will be finding the volunteers though. One place to start? Find out if there is a local chapter of the ACM or the IEEE Computer Society. People who are active in these groups tend to be the people who are interested in developing the next generation. Also industry advisory board for career technical schools or even community colleges. They are out there.

  • Computer Science Teacher - Thoughts and Information from Alfred Thompson

    Student Access to the AppHub for Windows Phone 7


    One of the many benefits of the DreamSpark program, besides all of the free software, is access to the AppHub for submitting Windows Phone 7 applications for sale for free. Businesses and other individuals have to pay to join the App Hub and submit apps to the system. The process for getting started can be a little confusing though. In this post I will try to explain it in language a reasonable human being can understand. In other words, the directions I myself would like to read.

    Note that college/university students sign up through DreamSpark on their own while high school students get access through their schools. The extra step is so that Microsoft doesn't find themselves in the tricky business of validating who is and is not a high school student and gathering a lot of personally identifying information on minors. In short the extra step is for everyone's best interested. My friend Gautam Reddy has a wonderful blog post that explains the step by step of signing a high school up for DreamSpark BTW.

    The first step is to get a DreamSpark account. You’ll need a free Windows Live id for that but the DreamSpark site will help you though that simple process. If you already have a DreamSpark account, sign in and let’s get started.

    1. First register for AppHub through DreamSpark.
      • Under the Download Software link on the DreamSpark home page find the Windows Phone link and select it.
      • Once there select the Register for the App Hub link. (You may want to download the development software while you are there as well.) 
      • Select Student as your account type on the App Hub registration page and enter your contact information
    2. You will get an email to verify your registration. Make sure you use a valid email address that you check. You may want to check to see that this email doesn’t get filtered to your SPAM folder – It happens sometimes.
    3. Now you can submit an app but you are not done yet (sorry) After you submit the first time you will receive an email from a company called GeoTrust. The final verification process is a it of necessary seriousness that neither you  or Microsoft really wants or needs to go through until you actually have an app to submit.
    4. After GeoTrust has verified your identity, you will receive a second email from GeoTrust that asks you to send an signed copy of an ID.  It’s all about making sure people are identified so that they can receive payment  for and take responsibility for their work. This second email can take up to 2-3 days
    5. After you send in the Signed Copy of your ID GeoTrust sends Microsoft the identification information, this can also take up to 2-3 days. At least you only have to do this once.
    6. Once the Signed Copy of the your ID is received the certification process for your application starts.
      • Please note: it can take a maximum of 5 business days to complete the certification
    7. If your application doesn’t meet the certification requirements, the application is rejected. You will be told what requirements are not being met so that you can fix them and submit the app again with the fixes (and you are back to step 6). 
    8. When the certification process ends and certification is successful it takes about 5/6 hours for the app to be placed up in the marketplace.

    Once your app is in the marketplace you’ll want to promote it to friends and potential customers. Make sure that you have a good explanation of the app and its value to others. Good luck!

Page 2 of 7 (19 items) 12345»