Tic-tac-toe in Scala – Part 1

What is Tic-tac-toe?

Tic-tac-toe is a two player turn based game played on a 3×3 grid with X and O tokens. Usually X plays first. The objective of the game is to be the first player to place three tokens of the same kind in a row, column or diagonal on the grid.

Here is a game in which the first player, X, wins on column 1 after 7 moves:

An Overview: Architecture

Now that you have been reminded about the game of tic-tac-toe, let me describe to you the design and architecture of the command-line application I wrote to play the game.

The application is composed of three sub-components. The game engine, the computer AI and the command-line interface.

The game engine implements and enforces the rules for the game of tic-tac-toe, i.e. it abstracts and modularizes the game’s logic. This helps to keep the parts of the game that impose the rules completely separate from the interface used to present and interact with the game.

The computer AI sub-component implements three levels of computer intelligence: novice, intermediate and expert.

And finally, the command-line interface is the sub-component that handles the intercommunication between the other two sub-components. It also provides the display and control mechanisms for a human user to view and play the game.

Another Overview: Implementation

I decided to implement the application in the Scala programming language. “Why Scala?”, you may ask. Well, for the simple reason that it is currently the language in which I am trying to become competent and proficient. As a rule, when I’m learning a new language I try to implement some non-trivial programs that will get me to utilize a wide variety of features of the language. Over the years I have found that writing a tic-tac-toe application is one of the best ways for me to accomplish that goal. As I proceed to delve deep into the implementation details of the application in other posts I will try to remember to point out various language features that were convenient or absolutely necessary in order to achieve the particular result I desired.

There are four packages that comprise the application:

1. tt.dwaynecrooks.games.tictactoe – It contains the core classes. Of importance are the Engine, Grid and Token classes.
2. tt.dwaynecrooks.tools.fsm – It contains a set of classes that together implement a simple domain specific language (DSL) for a command driven finite state machine. The Engine class makes full use of the DSL and is a lot more maintainable because of it. This DSL was a joy to implement. The Scala language really made this relatively easy to do.
3. tt.dwaynecrooks.games.tictactoe.ai – It contains the classes that implement the artificial intelligence for the novice, intermediate and expert computer players. There is a Strategy trait that the classes Novice, Intermediate and Expert implement.
4. tt.dwaynecrooks.games.tictactor.cli – It contains the TicTacToe class which implements the command-line interface for the game. The TicTacToe class is also the entry point for the application.

And finally, here is a diagram showing the relationship between the various classes:

The particular way in which the TicTacToe class makes use of the Strategy classes will be discussed when I am explaining the implementation details of the TicTacToe class.

Hopefully at this point you have a general idea of the design, architecture and implementation of the application.

This post has gotten long enough and I am simply getting exhausted explaining all this stuff and drawing all these diagrams. So, in Part 2 I will begin to dig deep into the implementation details. Until then, happy coding.

Notes

• The tic-tac-toe diagram was drawn using the Inkscape Vector Graphics Editor.
• The class diagram was drawn using Dia.

Project Euler – Problem 93

The problem: Problem 93

Analysis

This problem was straight-forward to solve and only required the use of some standard algorithms. A quick analysis shows that a brute-force method suffices to find the solution. Let be a subset of . There are such subsets. Let be a permutation on . Clearly, there are such permutations. For each we simply compute all possible ways of evaluating the expression using all possible ways of adding parentheses, where . Since, can each be selected in ways and there are exactly ways to add parentheses to the above expression, it follows that we have expressions involving . Overall, we will end up evaluating expressions, which a brute-force algorithm is capable of computing in a reasonable amount of time.

Algorithm

So here’s the algorithm:

largest = 0, ret = {}
for each 4-subset, X, of {0,1,2,3,4,5,6,7,8,9} do
  for each permutation, p, on X do
    for x, y, z in {+,-,*,/} do
      compute all expressions, p[X[0]] x p[X[1]] y p[X[2]] z p[X[3]] using all 5 possible parenthesizations
    end-for
  end-for
  determine n, such that n + 1 was not the result of one of the expressions evaluated in lines 3-7 and 1, 2, 3, ..., n was a result of one of the expressions
  if n > largest then
    largest = n
    ret = X
  end-if
end-for
return ret

To clarify how it works, let’s suppose that , , , and . Then we will have to compute the expressions:

Finally, after computing all expressions involving and , we determine . In this case , since is never computed as a result of one of the expressions and are results of at least one of the expressions.

Implementation Details

I solved this problem in Lisp. The function solve implements the
algorithm.

(defun solve ()
  (do ((largest 0) (ret nil)
       (s (vector 0 1 2 3) (next-subset s)))
      ((null s) (values largest ret))
    (let ((n (perform-evaluations s)))
      (if (> n largest) (setf ret s largest n)))))

The function perform-evaluations implements lines 3-8 of the
algorithm. It returns as described in line 8.

(defun perform-evaluations (s)
  (do ((seen (make-array (1+ max-result)))
       (p s (next-permutation p)))
      ((null p) (largest-consecutive seen)) ; returns n
    (dolist (f ops)
      (dolist (g ops)
        (dolist (h ops)
          (let ((a (svref p 0)) (b (svref p 1)) (c (svref p 2)) (d (svref p 3)))
            (dolist (x (parens a f b g c h d))
              (if (positive-integerp x) (setf (aref seen (1- x)) t)))))))))

parens is a macro that produces a list containing the parenthesizations of the expression it is given.

(defmacro parens (a f b g c h d)
  `(list
    (funcall ,h (funcall ,g (funcall ,f ,a ,b) ,c) ,d)
    (funcall ,g (funcall ,f ,a ,b) (funcall ,h ,c ,d))
    (funcall ,h (funcall ,f ,a (funcall ,g ,b ,c)) ,d)
    (funcall ,f ,a (funcall ,h (funcall ,g ,b ,c) ,d))
    (funcall ,f ,a (funcall ,g ,b (funcall ,h ,c ,d)))))

So, for example,

> (parens 1 '* 2 '- 3 '+ 4)
(3 -5 3 3 -5)

However, notice that parens fails whenever one of the parenthesizations yields a division by zero.

> (parens 1 '+ 2 '+ 3 '/ 0)
error: division by zero

> (parens 4 '/ 3 '- 2 '+ 1)
error: division by zero

To circumvent this problem I decided to implement new functions add,sub, mul and div such that whenever one of their arguments is nil the result is nil. Also, using div to divide by zero yields nil instead of an error. So,

> (parens 1 'add 2 'add 3 'div 0)
(nil nil nil nil nil)

> (parens 4 'div 3 'sub 2 'add 1)
(1/3 -5/3 5 2 nil)

The code for add, sub, mul and div is shown below.

(defun add (a b) (perform '+ a b))
(defun sub (a b) (perform '- a b))
(defun mul (a b) (perform '* a b))
(defun div (a b) (perform '/ a b))

(defun perform (op a b)
  (cond ((or (null a) (null b)) nil)
        ((and (eql op '/) (zerop b)) nil) ; avoid division by zero
        (t (funcall (symbol-function op) a b))))

Finally, the functions next-subset and next-permutation do exactly what their names imply. These are interesting algorithms in their own right and I will try to explain how they can be implemented in another post.

To solve the problem simply call solve and wait in anticipation (about 17 secs) for the answer.

> (time (solve))

Run time: 16.48103 secs.
(the answer has been removed, solve it yourself)

Scala: My new favorite programming language

A little less than two weeks ago I came across the Scala programming language. Since then I’ve been intensely learning the language and becoming familiar with the Scala way of doing things. I have never had this much fun on the JVM before. The language was relatively easy to learn and I was productive in a matter of days. I must confess though that I have done programming in Scheme, Lisp, Haskell and OCaml before so all of the functional programming ideas and techniques were not new to me, it was just in a different syntax.

Anyway, as a first project in the language I decided to implement a command-line tic-tac-toe game. So in the coming days I will explain its design and implementation, and demonstrate many features of the language that really helped to make the game a joy to program.

In the meantime, here are some resources I used while learning the language:

• http://www.scala-lang.org/ – The official website for Scala. It contains great documentation and is also the place you go to download the tools needed to use the language.
• The Programming in Scala book – A very well written book on Scala by Martin Odersky et al. It gets you up to speed on the language in no time.
• The #scala IRC channel on freenode – When I encountered difficulties translating my ideas into code the community was really helpful in moving me towards a solution. They were very friendly and eager to assist. I love the Scala community.