Computer programs playing two-persons games like Chess, or Go usually use a search algorithm like minimax possibly with alpha-beta pruning. The simplicity of the game Tic-tac-toe however, makes a search algorithm unnecessary. The number of possible board situations is very limited and a better option in this case is to use a lookup table.
I started by generating all possible board situations and placing them all in a database. After that, calculating for every position the best possible move or moves that should follow to minimize the chance of losing and maximize the chance of winning was straightforward. I used the result to make a lookup table to be used in a C++ program that plays Tic-tac-toe perfectly. Because of the 8-fold symmetry of the board the lookup table does not include too many elements.
In a previous post I spoke about JavaLogo. When talking about “turtle graphics”, L-systems automatically come to mind. For those who don’t know, L-systems or Lindenmayer systems are a mathematical formalism proposed by the biologist Aristid Lindenmayer in 1968 as a foundation for an axiomatic theory of biological development. More recently, L-systems have found several applications in computer graphics.
Central to L-systems, is the notion of rewriting, where the basic idea is to define complex objects by successively replacing parts of a simple object using a set of rewriting rules or productions. The rewriting can be carried out recursively.
Take the following example:
Rewrite rule: F -> F-F++F-F
Now we come to the point where its relation with “turtle graphics” becomes apparent. The F, means draw a line forward. +, means turn left, – means turn right. When we apply the rewrite rule 4 times and when turning left or right always turn 120°, drawing the L-system’s turtle graphics gives us the following figure which is called the Koch Snowflake.
Another example of a L-system is
Rewrite rule: F -> FF-F-F-F-F-F+F
Applying the rewrite rule 4 times and always turning 90°, gives us this figure:
When you’re looking at creating interesting figures with “turtle graphics”, checking out Lindenmayer systems further might prove worthwhile. Take a look at some examples I made using JavaLogo.
For more info:
To get to the other… um… uh…
The MIT isn’t the only university that’s putting free course materials on the web, the Dutch Open University is doing the same. One of the courses they have published so far is an introduction to (Java) programming. Java isn’t the easiest language to start programming in when you’re a complete newbie, but the designers of this course have taken an interesting approach. From this course’ website you can download a JavaLogo.jar file that contains some classes that allow you to code in a LOGO kind of way. The most famous feature of LOGO is it’s “turtle graphics”. Take a line of code like this one:
REPEAT 4 [FD 100 LT 90]
This LOGO program draws a simple square with sides of 100 units long: FD is short for Forward and LT stands for Left. In LOGO you basically control a “turtle” on screen leaving a trail when moving.
LOGO is a great introduction to programming because it gently introduces basic programming concepts like procedures and recursion. It’s very easy and a lot of fun to create interesting patterns such as all kinds of spirolaterals and fractals. With JavaLogo you can write web-enabled programs in a similar way in Java. I’ve been playing around with it and created this applet in a few lines of code that shows the Sierpinski triangle.