The Artima Developer Community
Sponsored Link

Musings on Language and Design
Groovy AI Tic tac toe
by Jeremy Meyer
November 26, 2009
Summary
A happy little voyage of discovery down the Groovy road.

Advertisement

Discovering Groovy

I have been enjoying Groovy much more than I thought. Really enjoying it, in fact. Looking around, I find that surprisingly few books have been published on it, and not enough is being said about it. Ok, it is a language that seems to be perceived to have lost its way a bit, but I think it has pretty much found it now.

Like Ruby, which experienced an upsurge of interest with the creation of Rails, Groovy suddenly got very interesting to me with the invention of Grails. I liked the idea of an easier way to use all the great frameworks I wanted to use like Hibernate and Spring and SiteMesh etc. It had started to sound like it was worthwhile taking a look. And I am very glad I did.

I love Ruby, and I love the whole model of dynamic scripting languages, especially ones which run on the JVM. But using Ruby and Rails, I kept finding my brain stretched just a little bit by having to learn new syntax at the same time as getting comfortable with new paradigms. It was taking too long to switch my brain into a different mode, and that made it very hard for me to persuade customers to take the plunge in all good concience.

I remembered how exciting Java was when I first learnt it, because it seemed so simple to use and well designed after C++, so I found myself wondering if perhaps Groovy had that same sense of newness and elegance and simplicity whilst being built on something familiar.

It did.

I had heard a few reports about Groovy, the negatives of which were usually prefixed by "you used to have to", or "you didn't used to be able to", and the positives which usually took the form of "..easy for a Java developer" or "seamless.. because you can just use Java". So it sounded like it was improving.

A friend (and wonderfully pragmatic hacker) said to me "the best thing about Groovy is that at a pinch you can almost just change a .java file to a .groovy file and run it". Quite true. You almost can. But you wouldn't want to. That would miss the point. And it's quite an important point.

Groovy Isn't Java

Groovy is definitely not Java. In fact it isn't even Java-ish. Possibly an odd statement , but let me justify it. Ok, it is a JVM language, which means that you can use all your Java libraries, (and best of breed frameworks), but then so are many other languages (like JRuby, Jython, Clojure or Scala) which aren't Java-ish either. The thing is that you don't expect them to be, but because Java code is almost 100% compatible with Groovy, one would have thought that Groovy would be very Java-ish.

Yes, it integrates truly seamlessly with your Java code, meaning that your classes can extend Java classes, and operations that take Java objects will willingly take Groovy objects, if typed in the right way. And of course you can usually get away with just writing Java code. But, and here's the rub. This makes your Groovy code non-idiomatic. The Groovy idioms are distinctly different and if you are going to embrace Groovy, it seems you will have to leave some Java habits behind.

The upside, and it is a very, very important upside in my book, is that as a Java developer you are not sacrificing productivity from the outset, and as you learn the paradigms, you can refactor your code. This is an enormous benefit. It might offend the purist, who would claim that using a new, dynamic language and not bothering to learn its idioms is pointless, and even destructive, but if I can convince people that their Groovy code will at worst look like Java, and at best give them all the advantages of Groovy, then suddenly I have a strong argument for them diving in and trying something new.

So how is it not Java-ish?

Obviously Java code is too noisy to be great for scripting. It wasn't designed that way. For a dynamic scripting language, you want simplicity and clarity, and to my mind Groovy has successfully delivered.

So, apart from all the powerful features in Groovy (of which more later) the language itself is really nice to write in. Anyone who knows, (and yes, even loves) Java will appreciate how many of its little linguistic annoyances have been tackled by Groovy.

Downcasting, for loops, iterators, checked exceptions, etc.. are all frequent pain points. Java code is strewn with semi-colons and type declarations. Iterating through hash tables is not ideal even since the introduction of the collections looping constructs. Although Java has the concept of a closure, with the anonymous inner class method, again there is a load of messy brackets and typing that has to be done to use them.

So.. you might ask, "Wouldn't it be Groovy if we could.."

And of course the reason I have listed these particular questions is that the answer in each case is "we can and it is".

Using Groovy

So, I wanted to discover for myself whether or not I could easily use these features and create something which was more or less Groovy, in a decent amount of time. In other words, is this all just lip service, or does it work? Is it worth learning a dynamic scripting language that works with Java and the JVM, when I could just be using Java? Is it really going to be easy enough to learn to actually save me time?

I decided to focus on the basics of the language, the syntax, and some of the basic Groovy idioms. If that was a good experience then the mental shift of working with a dynamic scripting language would seem more worthwhile.

Like most of the people reading this blog, I am sure, I like to learn a language by programming in it. So I chose an amusing little project which I first came across about 15 years ago.

Learning Machines

Donald Michie's MENACE (Matchbox Educable Noughts And Crosses Engine) was an early 1960 example of machine learning. (Noughts and Crosses is what we Brits call Tic Tac Toe.)

The original machine was an array of matchboxes (about 300) with a picture on each one of a possible Tic Tac Toe position, and some beans or beads in the box; one to represent each of the free squares (by number, color or whatever). So if there were 4 possible moves left on the board, there would be 4 beans in the box, each uniquely identifying one of those four squares.

A human player would make a move on a piece of paper, or Tic Tac Toe board, then pick up the matchbox bearing the picture matching the current position, shake it and take out the bean which represented MENACE's next move. So far it just sounds like a random generator, but the clever part of it is that if MENACE lost a game, the human player would "punish" the machine by throwing away the last bean that was taken out of a matchbox. That means that given the same situation in the next game, MENACE could not make that move again. Thus MENACE would learn in a rudimentary way, to play Tic Tac Toe, by gradually running out of bad moves.

Since not all positions necessarily have any good moves which can be made, occasionally an empty matchbox is discovered, signifying that the only moves left are bad. In that case the offending bean from the previous box would be disposed of. This would prevent MENACE from getting into such a predicament the next time around.

Coincidentally, it seems that someone has recently re-created an original "hardware" version of MENACE with the slight improvement over the algorithm above. In this case, wins are rewarded by adding a bean to each matchbox representing every move made in that game. This increases the chance of MENACE making winning moves, but does not change the end result.

You might be thinking "Tic Tac Toe is a simple and silly example. Why not use 3 for loops and 2 if statements and make a perfect player from the get go?". Well you certainly could do that, but this is about giving ourselves something challenging enough to do with Groovy to make the project worthwhile. Also it is a lot more fun playing the game repeatedly to see how long it takes before it starts forcing a draw, than it would be playing a game which will always win or draw. (Of course no game should ever win if it is playing against someone who has taken 5 minutes to master the game).

The Project

The project is a Groovy simulation of the MENACE computer. Instead of using beads in a matchbox we keep a list of all bad moves, a simple array of positions which we serialize between games. We have two interfaces, text and GUI.

Although the code is more succinct than it would be in Java, if you include the Swing interface to the game (which makes it much easier to play) the whole project is about 300 lines of code. I have included it all [here] but I want to highlight the parts of code that I think are a great improvement over Java and which made it quite a joy to code. I have avoided some of the really powerful features of Groovy, and not focussed on its dynamicism and hence its suitability for DSLs, an interesting topic for another conversation.

I used the Groovy Eclipse plugin at http://groovy.codehaus.org/Eclipse+Plugin, but you can run this code from the command line or use the plugin of your choice. To run from the command line, (assuming you have Groovy installed, I used version 1.6.3) unzip the zip file, keeping its folder structure, and from its root directory, type "groovy tictactoe/GamePanel".

The code is made up of 3 classes. Position, Game and GamePanel.

Position is a fancy wrapper around an array of pieces, and is also the MVC model for GamePanel which is the GUI interface class. Game is the controller which allows the human to move, checks the computer's response to see if it is bad and stores the bad move if the computer loses.

The Position Class

Groovy classes are stored in files with a .groovy extension. You could of course just run Groovy code without any classes, because it is a scripting language, but since we are creating a proper program, we are using classes.

Position is obviously a bit more than just a wrapper for an array, but thinking about it as such is a good start. I have used ellipses to show that it is a fragment, and colored the Groovy code green for comparison with the blue Java code.


public class Position implements Cloneable {
   ..
   def pieces = [0,0,0,0,0,0,0,0]
   ..
}

The class definition looks pretty much like Java, but there are no semicolons and there is no need to define what the pieces array type is. Not perhaps a huge saving in time / effort and readability, you might think, except that the Java equivalent fragment would actually have to be:


public class Position implements Cloneable {
   ..
   int[] pieces = {0,0,0,0,0,0,0,0}

   public void setPieces (int[] pieces) {
      this.pieces = pieces
   }

   public int[] getPieces () {
      return pieces
   }
   ..
}

..because Groovy generates a getter and a setter for you, and even better, if you create your own getters and setters, it allows you to use bean property syntax.. so,

position.pieces[3] = 1

in Groovy, would actually be calling your getter to get the pieces array. That was 6 lines down to 2, assuming we are happy with a default getter / setter. Just compare the number of times "int[]" and the word "pieces" occurs in each example, too. Excellent simplification! Of course, if you aren't careful it can bite you, you have to make sure you actually want bean properties.

After a little study, it becomes apparent that any Tic Tac Toe position has 7 tactically identical positions which can be created by flipping and rotating the board. Since we want to find bad moves, it speeds things up if we consider all equivalent moves. The diagram shows an example of 3 equivalent positions (out of a possible 8).

A nice way to represent a board for easy comparison is to treat the 3 by 3 grid as a simple 9 digit, base 3 number, with 0 being empty, 1 being X and 2 being 0. If we flip and rotate all the positions of the board, convert to this number, and take the smallest value of the 8 unique positions, we have a good way of "factorising" the position. We can use this to compare positions for equivalence, and for a bad move, we just need to store this integer.

Lets look at some of that code.

To convert the position to a value:


private int getIntValue(def pos) {
   def total = 0
   9.times {
      total += pos[it]*3**it
   }
   total
}

This is very tidy code, and a great improvement. We want to make the method private, which we do using the familiar access specifier, but we don't need to specify the type for total. We can use the very elegant "9.times" syntax to give us our loop and in the curly braces (actually a closure) we have the default index operator "it" which we can use. On top of this, we can use ** for raising to a power and we don't have to specify the return keyword to return a value. Now we can add simple mirror and rotate translation arrays to our class. Proof that you only need these to attain every equivalent Tic Tac Toe position is left to the bored or un-trusting reader! But you can take my word for it that given any position, we need to rotate it 3 times, then mirror it and then rotate it 3 more times to have achieved every equivalent position. Since all we are doing is moving elements, we can add create two translation arrays:

public class Position implements Cloneable {
   ..
   final static int[] MIRROR = [2,1,0,5,4,3,8,7,6]
   final static int[] ROTATE_90 = [6,3,0,7,4,1,8,5,2] 
   def pieces = [0,0,0,0,0,0,0,0]
   ..
}

and then translate as we need:

private int[] translate(def pieces, def translation) {
   def newArray = []
   9.times {
         newArray[translation[it]] = pieces[it] 
     }
   newArray
}

so to rotate we can do:

..
translate(currentBoard, ROTATE_90)
..

The position can also return the winner. 0 if the game is still in progress, 1 if X and 2 if O.

Here is an annoying little artifact in Groovy.. Note that the fragment for checking if there are empty squares is nice and minimal.

..
for (p in pieces) {
   if (!p) 
      return 0
}
..

This makes use of Groovy's intelligent coercion which will coerce a null or a zero integer to the boolean value "false". Reminiscent of C perhaps, but with a little more safety. BUT..

There was an interesting gotcha here. Well, it got me anyway. I wanted to do the following:


..
pieces.each {
   if (!it)
      return 0
}
..

To be a bit more Groovy, and use the default closure variable "it". But it won't work here. The reason is that the .each is actually a method that takes a closure as a parameter, (the {} block that follows it) and since closures can be called like methods, the return statement just returns from the closure. In fact, all it will do is just iterate through the loop again. This had me scratching my head for a long time, and it was very annoying indeed. Still, so far, there have been many more things that I have enjoyed

Lastly, the position can also display itself. This is not necessary if we are using the GUI interface, but of course it is good for debugging.

To get a primitive (but perfectly adequate) display which looks like this:


---------
[O][ ][O]
[O][X][X]
[X][ ][O]


We need:


private void display() {
   println "---------"
   3.times {y->
      3.times {x->
         print getXY(x,y)==0? "[ ]" :(getXY(x,y)==COMPUTER?"[X]":"[O]") 
      }
      println ""
   }
}

You will notice two things here. Firstly, we don't have to do all that blathery "System.out.println" business. Granted, most Java developers can type it in their sleep with a single, multi finger thump on the keyboard, but why do we have to think about System.out? It is horrible.

Secondly, you will notice that the nested times loops are passing parameters to the closures. This is neat syntax. In this case it would override the default it variable, and although we only need one, I found using x and y to be more intuitive than using x and it.

Let's amuse ourselves for a moment by looking at the Java equivalent.



private void display() {
   System.out.println("---------");
   for (int y = 0; y < 3; y++) {
      for (int x = 0; x < 3; x++) {
         System.out.print(""+ (getXY(x,y)==0? "[ ]"):(getXY(x,y)==COMPUTER? "[X]":"[O]")); 
      }
      System.out.println ("");
   }
}

Wow. Noisy.

Let's have a look at some of the highlights of the Game class.

The Game Class

The Game class's job is to load the list of bad moves, get a move from each player in turn, check that the game hasn't been won, and if it has, store the last, bad move (if the computer lost). The game can be played in text or GUI mode.

Since we are using Java serialization to persist the bad moves, we can just use an ObjectOutputStream, so it should look just like the Java..



private void persistBadMoves() {
new ObjectOutputStream (new      
   FileOutputStream(FILE_NAME)).withStream {             
      it.writeObject(badMoves)
   }
}

Except that it doesn't quite. The first thing you probably noticed is that you don't have an Exception declaration or 6 lines of exception handling with an IOException stuffed into a RuntimeException and re-thrown. (Even describing that takes a long time!) The other thing you might have noticed is that Groovy adds the withStream method to streams which takes a closure as a parameter. The stream is referenced via the default parameter it inside the closure. withStream is also polite enough to close the stream at the end of the closure code. Ok, I might not be inspired enough to attempt a "poignant" guide to Groovy, but I have to say, when I write which is as simple as the code above, and it does what I want.. it makes me excited, and I think "Cool!".

To achieve the same effect in Java (i.e. do the same job, not make me think "Cool!") we would have to do:



private void persistBadMoves() {
ObjectOutputStream oos = null;
try {
   oos = new ObjectOutputStream (new FileOutputStream(FILE_NAME));
   oos.writeObject(badMoves);
   }
   } catch (IOException ioe) {
      throw new RuntimeException(ioe);
   }
   finally {
   if (oos != null)
      oos.close();
   }
}

This time I count 11 lines of Java to 4 lines of Groovy. If we wanted to do something fancy and really did need to implement the try / catch / finally, we could use another Groovy paradigm, which is the null-safe dereferencing syntax.


..
finally {
   oos?.close()
}

The "?" means "call the method if not null". Excellent!

The GamePanel Class

This is the smallest, simplest class, and makes the most use of the seamless integration with Java. The GamePanel is the view of the MVC pattern. It is also a JPanel, which is to say that it is a Groovy class which inherits from Java's javax.swing.JPanel. That is simply done with the declaration:


public class GamePanel extends JPanel {

It loads up 3 images which it uses to create the board. Unsurprisingly these are:

, and

I went with a hand-drawn look to make it look a little quirky. Again we are saved lots of the bother of exception handling by Groovy, so all we need to do to load the images up is :


..
images[0] = ImageIO.read(new File(path+"board.bmp"))
images[1] = ImageIO.read(new File(path+"nought.bmp"))
images[2] = ImageIO.read(new File(path+"cross.bmp"))
..

Since our main game loop is waiting for input from the user, and that input is coming from a mouse event, we have two threads which need to synch with each other. The easiest way to implement this is to make use of the Java concurrency class SynchronousQueue. A very tidy way of having two threads producing, consuming and blocking. Groovy has no problem integrating with this class.


queue  = new SynchronousQueue()

A bit of translation lets us find out which square of the Tic Tac Toe grid is being clicked on, and we can put that integer into the queue.


queue.put(((int)((it.x-35)/100) + (int)((it.y-35)/100)*3))

A simple getter calls the take() method which causes the calling thread to block whilst waiting for the integer:



public int getMove() {
   queue.take()
}

There is another delightful construct which I really like. Groovy has some great short hand syntax for Maps.You can define a map in Groovy by simply saying:

fruit = [a: "apple", b: "banana", p: "plum"]

Under the covers, Groovy will use a HashMap or whatever class is most appropriate, but for a small map, this is very useful. Now using the as keyword, I was able to make use of a great little Groovy abstraction:


..
addMouseListener ([
   mouseClicked: {queue.put(((int)((it.x-35)/100) + (int)((it.y-35)/100)*3))},
   mouseEntered: {},
   mouseExited:  {},
   mousePressed: {},
   mouseReleased:{}
   ] as MouseListener)
..

This looks a bit odd at first, the Java addMouseListener method above is being passed a map of closures, where the map key is the method name of the MouseListener interface and the value is the closure containing the code to be run, i.e. the method body. That is a great abstraction of an interface implementation, a mapping of method names to closures. This is not hugely different from using an anonymous inner class, but after all, we are using these particular closures in an identical way to an inner class, and again, the syntax is cleaner and less noisy than that of Java.

It is a simple matter just to override an inherited Java method with Groovy code so the paint method of our panel is very similar to what it would be if it was Java, just Groovier.


public void paint(Graphics g) {
   g.drawImage(images[0],0,0,null)
   model.pieces.eachWithIndex {p,i ->
   if (p>0) {
      g.drawImage(images[p],x_coord[i],y_coord[i],null)
   }
}

The model to view transformations come from the x_coord and y_coord arrays, so that we can position the images in the right places. The panel is laid out in a JFrame giving us a pleasant looking interface.

Groovy has a lot more to offer

I have deliberatlely not focussed on any of the dynamic features of Groovy for the purposes of this discussion, or on how easy it is to create DSLs, or domain specific languages, but those are the reason you really want to be using a language like Groovy, and once you have enjoyed it, like I have, hopefully you will start exploring it.

I hope you have fun with the code, or even just playing the game.

So what do you think? Does this make you consider using Groovy?

Talk Back!

Have an opinion? Readers have already posted 12 comments about this weblog entry. Why not add yours?

RSS Feed

If you'd like to be notified whenever Jeremy Meyer adds a new entry to his weblog, subscribe to his RSS feed.

About the Blogger

Jeremy has been designing and developing software for over 20 years, as well as teaching its mastery. He is fascinated by all aspects of architecture, design and development, the philosophical, the psychological and the aesthetic. He currently heads up the training division at hybris Software, a fast growing and very exciting eCommerce company.

This weblog entry is Copyright © 2009 Jeremy Meyer. All rights reserved.

Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us