2013-10-29

Playing HexDame, 1: Introduction

For one of my university courses, I will be implementing an automated HexDame player.  This post is the first in a series that will document the process in a way that is hopefully easy to understand.

HexDame is a variant of draughts/checkers on a six-sided board with six-sided tiles:

Because the board shape differs from that used in checkers, some of the rules of checkers need to be adapted.  In HexDame, pieces can move in six directions rather than four: north-east, north, north-west, south-west, south, south-east.  Like in checkers where men (as opposed to kings) can only move forward, in HexDame men can only move away from the player's initial corner.  For example, white's pieces can only move away from the tile labeled "a1" in the picture.  A man gets promoted to king when it reaches "the other side", which in HexDame is the two sides furthest away from the player's initial corner.

Now let's think about how to play this game as a computer.  You might start brainstorming about how to set up a trap, or how to develop a strong position, or that promoting a man should have highest priority if it can be done in one move.  You could do this, but you would end up with a bunch of isolated ideas with no guidance as to how to combine them.  Worse, the ideas you come up with are tailored to this particular game.

That's right, there are ways to automate the playing of games that are general, in that they work for many games.  The methods that I am thinking of rely on the concept of a game tree.

As an example, here's an image of part of the game tree for tic-tac-toe:


At the top ("root") of the tree, there is the empty tic-tac-toe board.  Below it are all the possibilities for how the tic-tac-toe board will look after one move.  Actually there are more possibilities, but each of the ones not shown can be rotated to match one of those shown.  The rotated variants lead to the same game results, and so do not need to be considered separately.

Below the possible boards after the first move are the possible boards after the second move.  Again, not all are shown.  The image stops there, but you can imagine how the game tree continues further down.

Game trees are a useful idea in many ways.  They model the whole game, revealing all the possible consequences of every possible move.  If you know the game tree, you know what to play.  So what's the catch?  Let's digress...

Lay conversations about the game of chess often touch on game trees.  Wild claims are routinely made about "how many moves ahead" a master looks.  It is a good rule of thumb to believe that stronger players look further ahead than weaker ones, but looking ahead is not the only thing to chess.

Well, actually it is, but it takes a lot of time to consider every possible move and countermove.  In fact, every additional step looked ahead costs roughly 35 times as much time!  So if it takes you on average one minute to look two steps ahead, it will take you more than an hour to look three steps ahead, and more than a day to look four steps ahead.  The magic number 35 here is the average number of moves you have to choose from in chess.  In some situations there are fewer possible moves, in others there are more, but the average is around 35.

So what do masters do?  They don't consider each possible move, because some moves are obviously stupid.  They consider forcing moves first (moves that put the king in check or attack the queen), because forcing moves constrain the opponent, which reduces the number of moves they have to choose from, which reduces the time spent thinking ahead.  In the beginning of the game, they following opening theory, which determines their early moves much like a phone script determines a telemarketer's sequence of questions.  Toward the end of the game, they similarly follow endgame theory.  For the rest of the game, they use their highly developed intuition for chess, and a large set of explicit principles, such as the ones listed at http://www.geocities.com/siliconvalley/lab/7378/principl.htm.

In principle there is no difference between humans and computers.  Both have to comply with the laws of physics, and both are subject to the tyranny of computational complexity, which measures the amount of thinking time and the amount of memory that is required to compute some result.  The practical difference is that out of the box, humans have the ability to recognize patterns.  This is a complicated ability that developed over the years through the process of evolution.  In the context of games, it is good for two things; de-greasing engines and killing brain cells developing intuition and applying existing knowledge.

Intuition in games is a cool thing.  A decent chess player can look at a position and instantly see in whose favor it is.  Not with perfect accuracy, but perfect accuracy would take more time than has passed since time began.  It is better to lose the occasional game due to inaccuracy than to lose every game by running out of time.

The other way in which human brains have a headstart for playing this kind of game is that they can apply existing knowledge to it.  Knowledge that has been learned for one task can sometimes be reused for another.  For instance, if you're good at playing soccer, it will be easier for you to pick up table soccer.  Wait.. let me find a better example.  How about: if you're good at playing badminton, it will be easier to learn tennis.  If you know how to play chess, you have knowledge that can be repurposed for the game of checkers.  The rules are different, but the games are pretty similar.  Both have the concepts of capturing and promoting pieces, and, less superficially, both have positional and tactical aspects.

Artificial Intelligence researchers are working on mathematical analogues to these abilities.  The general field is reinforcement learning, in which an agent (such as a robot) learns to perform a task by trying things and being told how well it is doing.  In the subfield of transfer reinforcement learning, the agent tries to reuse knowledge from previously learned tasks.  Also lots of progress has been made on neural networks recently, which could substitute for human intuition.  These topics will probably pop up again in future blog posts; I'm not going to go into them here.

For the beginnings of our automated HexDame player, let's forget about these complications and just create a program that looks ahead.  The game tree provides a nice, systematic way for doing this.  More later.