Simple Tic-Tac-Toe AI in JavaScript

Click here to see the Tic-Tac-Toe game in action! (open in new window)

Last year, I was challenged by the thread at Thaiadmin to implement a two-player OX (or Tic-Tac-Toe, XO, what you may call) game. I had done this kind of program in VB6 before, so I decided to implement the one-player JavaScript version.

The hardest part of of this project is debugging the JavaScript. I had to write the value of each variable and things done in each step to the screen (as you see in the bottom of the figure above) to diagnose the problems. I was so embarrassed that I did not know any of the great web developer's tools such as FireBug.

The ideas behind the decisions making part (or the AI) are to search every possible moves and take the best one. In each move, We assumed that the opponent chose his best move and we chose our best move. This method is "Minimax" method. As described in Wikipedia:

Minimax (sometimes minmax) is a method in decision theory for minimizing the maximum possible loss. Alternatively, it can be thought of as maximizing the minimum gain (maximin). It started from two player zero-sum game theory, covering both the cases where players take alternate moves and those where they make simultaneous moves. It has also been extended to more complex games and to general decision making in the presence of uncertainty.

The Minimax method can be applied to many other board games too. But in some complex games such as Chess, there was so many game states that you cannot search into them entirely (it would take many many years on an ordinary computer). So some heuristic must be used to approximately determine value of each state and the search must be limited at a fixed level (deeper level of search makes the AI cleverer).

In my case, there was not too many game states so I can search on them entirely. You can test my game here - http://m3rlinez.googlepages.com/oxai.htm. Choose View->Source to view the JavaScript source code.

Fast nth Fibonacci number calculation

I am now preparing myself for Dynamic Programming quiz this Wednesday. One classic example of DP is the calculation of nth Fibonacci.

The straight-forward way is to convert the recurrence relation, Fn = Fn-1 + Fn-2, F0=0, F1=1, to a recursive function. However, the problem overlapping makes this solution poor in performance. A betterway is to calculate value of Fk from 2 to n in a bottom-up style. The asymptotic running time of this DP method is O(n).

   private static int FibN(int n)
   {
       if (n <= 1)
           return n;

       int a = 0, b = 1, c = 1;
       for(int i = 2 ; i <= n ; i++)
       {
           c = a + b;
           a = b;
           b = c;
       }

       return c;
   }

My instructor, Aj.Somchai, wrote in one of his book, "การออกแบบและวิเคราะห์อัลกอริทึม (Design & Analysis of Algorithms)", the challenge of finding a method that calculate Fn in less than O(n) time. After thinking for a while, I fired up my browser and search :)

This page described a method of calculating Fn in O(log n) time using a property of special case of matrix multiplication. The following is my implementation of this O(log n) method and O(n) method in C#.

using System;
using System.Collections.Generic;
using System.Text;

namespace FastFibo
{
   class Program
   {
       private static int[] G = new int[] { 1, 1, 1, 0 };

       /// <summary>
       /// Get [[1,1][1,0]]^n matrix.
       /// </summary>
       /// <param name="n">n</param>
       /// <returns>[[1,1][1,0]]^n</returns>
       private static int[] GetFiboMatrix(int n)
       {
           if (n == 1)
               return G;
           int[] c = GetFiboMatrix(n / 2);
           c = MatrixMul(c,c);
           if (n % 2 == 1)
               c = MatrixMul(c, G);
           return c;
       }

       private static int[] MatrixMul(int[] a, int[] b)
       {
           if (a.Length != 4 || b.Length != 4)
               throw new Exception("Invalid matrix size");

           int[] res = new int[4];
           res[0] = a[0] * b[0] + a[1] * b[2];
           res[1] = a[0] * b[1] + a[1] * b[3];
           res[2] = a[2] * b[0] + a[3] * b[2];
           res[3] = a[2] * b[1] + a[3] * b[3];
           return res;
       }

       private static int FibLogN(int n)
       {
           if (n <= 1)
               return n;

           return GetFiboMatrix(n)[1];
       }

       private static int FibN(int n)
       {
           if (n <= 1)
               return n;

           int a = 0, b = 1, c = 1;
           for(int i = 2 ; i <= n ; i++)
           {
               c = a + b;
               a = b;
               b = c;
           }

           return c;
       }


       static void Main(string[] args)
       {
           for (int i = 1; i <= 46; i++)
               Console.WriteLine("{0,4} FibN = {1,10} FibLogN = {2,10}",
                   i, FibN(i), FibLogN(i));
       }
   }
}

The normal 4-byte integer can only contain values in range [-2^31,2^31-1] and we can only get actual nth Fibonacci number up to n = 46. The difference of running time between O(n) and O(log n) for n under 47 can hardly be noticed.

This, however, can be apply to some Computer Olympiad problems such as "Find the last digit of nth Fibonacci number" :) You can also make this faster by convert it to non-recursion version.

RocketDock: Cool desktop dock menu!

Have been using RocketDock since last week. I found that it is so convenient to launch applications from dock menu. The icons are bigger than those on quick launch bar. You can actually configure the size of icons too!

Get RocketDock here (freeware)

Programmer Personality Type

Found an interesting test to do at Nut's blog.

My programmer personality type is ...

PHTB

You're a Planner.
You may be slow, but you'll usually find the best solution. If something's worth doing, it's worth doing right.


You like coding at a High level.
The world is made up of objects and components, you should create your programs in the same way.


You work best in a Team.
A good group is better than the sum of it's parts. The only thing better than a genius programmer is a cohesive group of genius programmers.


You are a liBeral programmer.
Programming is a complex task and you should use white space and comments as freely as possible to help simplify the task. We're not writing on paper anymore so we can take up as much room as we need.

You can take this test at http://www.doolwind.com/index.php?page=11 :)

My experiences from working on my last project influence most of my answers.