Confused Ramblings

Last time I left off after describing why it would be useful to be able to look at a board position and be able to quickly and easily determine if that position had been seen before. I’m going to devote this post to showing how this can be done.

The obvious solution is to examine every square of the board against a collection of previous positions. As you can imagine, this isn’t going to be quick. It would also involve storing all the previous positions which is something I said right at the start of this series that I didn’t want to do. You might want to give some thought about how you’d solve this problem yourself and imagine how you’d solve the same problem for games like chess (64 squares with different types of pieces on them), or Go (361 squares).

Fortunately other people much brighter than me have had to solve the same problem and come up with some very clever answers. In particular Albert Lyndsey Zobrist came up with a technique called Zobrist Hashing. This has some very nice properties; you don’t have to store the actual board position of previously encountered positions, and it’s very efficient to implement.

So what’s the secret? Well to start with there’s lots of big random numbers. There are two random numbers associated with each square, one for each coloured piece. The idea is to represent the position by a hash value formed by XOR-ing together the random numbers associated with each piece present on the board. The use of XOR has the nice property that you can calculate the hash value of another position created by the addition or removal of a piece by simply XOR-ing the associated random number.

The danger of using hash values is that you may get collisions. For a more complicated game like chess, the consensus seems to be that if you used 32 bit random numbers then the chances of collision would be too great, but 64 bits is enough so long as you code things so that a collision doesn’t cause “bad things” to happen. Being a natural pessimist I prefer to also use an additional check called a lock value to detect potential collisions. Basically this uses a separate set of random numbers to calculate a second hash value (the lock value). A position is only considered to match if both the primary hash and the lock values agree. I guess it’s time to look at some code. First the creation of the random numbers.

import random

random.seed(0)

hashKeyComponents = [[random.randint(0, sys.maxint)
    for square in range(42)] for piece in range(2)]

hashLockComponents = [[random.randint(0, sys.maxint)
    for square in range(42)] for piece in range(2)]

Well that’s all well and good, but how do you actually use these? The idea is that before you go through the expense of evaluating a position, you check to see if you’ve already seen the same position before. This information is held in a map which I’ve imaginatively called table and which is a class variable of Board. In addition to the map, two other attributes, hash and lock are added to positions.

class Board:
    table = {}  # hash => (value, iswin, lock)

    def __init__(self):
        …
        self.hash = 0
        self.lock = 0
        …

As the comment indicates, table is used to map a Zobrist hash of a position to a tuple comprising the static evaluation of the position, whether the position is a winning one or not, and the lock value of the position. How this is used and updated is best seen in the final version of the makeMove function.

    def makeMove(self, square):
        color = WHITE if self.count & 1 == 0 else BLACK
        self.position[square] = color
        self.heights[square % 7] += 1

        index = (1 - color) >> 1
        self.hash ^= hashKeyComponents[index][square]
        self.lock ^= hashLockComponents[index][square]

        self.count += 1

        value, iswin, lock = Board.table.get(self.hash, (None, False, None))

        if lock == self.lock:
            self.value = value
            self.iswin = iswin
            return

        value = self.value
        iswin = False

        if color == WHITE:
            for four in foursBySquare[square]:
                nWhite, nBlack = 0, 0
                for s in four:
                    piece = self.position[s]
                    if piece == WHITE:
                        nWhite += 1
                    elif piece == BLACK:
                        nBlack += 1

                if nBlack == 0:
                    value += weights2[nWhite]
                elif nWhite == 1:
                    value += weights1[nBlack]

                if nWhite == 4: iswin = True
        else:
            for four in foursBySquare[square]:
                nWhite, nBlack = 0, 0
                for s in four:
                    piece = self.position[s]
                    if piece == WHITE:
                        nWhite += 1
                    elif piece == BLACK:
                        nBlack += 1

                if nWhite == 0:
                    value -= weights2[nBlack]
                elif nBlack == 1:
                    value -= weights1[nWhite]

                if nBlack == 4: iswin = True

        Board.table[self.hash] = (value, iswin, self.lock)

        self.value = value
        self.iswin = iswin

Essentially, the difference from the previous version and this one is the calculation of the hash values, using them to check if there is a table entry and if so using the stored values rather than calculating them again. If it’s necessary to do the calculation for the first time then the values are cached for later reference. The only slight complication is the calculation of the index variable. This is used to convert the colour of a piece from -1 or 1 into 1 or 0 so that it can be used to reference the correct array of colour specific random numbers.

Just for completeness I should also include an updated version of the undoMove function which effectively resets the hash and lock values back to what they were prior to the move.

    def undoMove(self, square):
        self.count -= 1
        color = self.position[square]
        self.position[square] = EMPTY
        self.heights[square % 7] -= 1

        index = (1 - color) >> 1
        self.hash ^= hashKeyComponents[index][square]
        self.lock ^= hashLockComponents[index][square]

Well that’s laid most of the groundwork necessary. Next post I’ll begin to explain about the algorithms behind how the computer chooses which move to make.

Welcome back to my short series presenting my thoughts on game programming where I try and describe the thought processes and techniques used to develop a simple game using Connect 4 as an example. In this entry I intend picking up on the two topics I left hanging last time; how to determine if a board position is a winning one, and how to determine how good a given position is. First let me present an updated version of the Board class showing where we’ve got to so far and including some extra data I’ll be talking about in what follows.

class Board:
    def __init__(self):
        self.position = [EMPTY for square in range(42)]
        self.heights = [0 for col in range(7)]
        self.count = 0
        self.value = 0
        self.iswin = False

    def moveList(self):
        return [ c + 7 * h for c, h in enumerate(self.heights) if h < 6 ]

    def makeMove(self, square):
        color = WHITE if self.count & 1 == 0 else BLACK
        self.position[square] = color
        self.heights[square % 7] += 1
        self.count += 1

    def undoMove(self, square):
        self.count -= 1
        self.position[square] = EMPTY
        self.heights[square % 7] -= 1

    def isDraw(self):
        return self.count == 42

    def display(self):
        for start in (35, 28, 21, 14, 7, 0):
            for square in [start + i for i in range(7)]:
                c = self.position[square]
                if c == WHITE:
                    k = 'W'
                elif c == BLACK:
                    k = 'B'
                else:
                    k = '_'

                print k,
            print
        print

What’s happened to the isWin function and what’s this iswin attribute? Well it turns out that when a move is made you can make use of the last move made to very quickly determine if it was a winning move and make a note of that fact. The key to this is a data structure which is initialised using the data in fours.

foursBySquare = [set() for s in range(42)]

for four in fours:
    for s in four:
        foursBySquare[s].add(four)

What this is doing is creating an array of sets with one entry in the array for every square on the board. It associates a square with the set of all four square lines including that square. Since a winning move must include the last square just played (otherwise the game must have already ended), it is a simple matter to check just the lines including that square. Also, you can simplify testing whether or not an individual line is a winning line because it must comprise squares occupied by the same colour pieces as the pieces just played; no need to test for empty squares.

A given board position is going to be good, bad or neutral from the point of view of the program playing the game. It is the job of the static evaluation function mentioned at the end of the previous article to place a numeric value on this. For our purposes we will decide somewhat arbitrarily that a positive score will indicate that the player of white is best positioned and a negative value that the player of black has the advantage.

Static evaluation functions are by nature very game specific and having a good, efficient static evaluation function is crucial to designing a good program to play a particular game. That said, there is no one correct solution and it can be a trade off between how easy the function is to compute versus how accurate the result is. For Connect 4 a suitable measure of how good a board position is, would be to keep track of how many possible winning lines there are for both sides and subtract the value for black from that for white. We can afford to be a bit cleverer than that though. A line with 3 white pieces and an empty square is going to be more “valuable” than one comprising just one white piece and three empty squares.

So how to go about calculating this value. At first sight it looks like we might be back to having to examine all possible lines of four squares, but a little thought shows that if you already know the value of a position, then it is possible to calculate the value of a new position by only examining those lines which include the square just played. Rather like the process when determining if a move is a winning move in fact. You might have noticed the presence of the value attribute in the board class right alongside the iswin attribute? There’s a reason for that; both can be determined at the same time as a move is made as the calculations for both involve knowing the current position, the next square to be played, and examining the same set of lines associated with that square. Adding these details, the makeMove function now looks as follows.

   def makeMove(self, square):
        color = WHITE if self.count & 1 == 0 else BLACK
        self.position[square] = color
        self.heights[square % 7] += 1
        self.count += 1

        value = self.value
        iswin = False

        if color == WHITE:
            for four in foursBySquare[square]:
                nWhite, nBlack = 0, 0
                for s in four:
                    piece = self.position[s]
                    if piece == WHITE:
                        nWhite += 1
                    elif piece == BLACK:
                        nBlack += 1

                if nBlack == 0:
                    value += weights2[nWhite]
                elif nWhite == 1:
                    value += weights1[nBlack]

                if nWhite == 4: iswin = True
        else:
            for four in foursBySquare[square]:
                nWhite, nBlack = 0, 0
                for s in four:
                    piece = self.position[s]
                    if piece == WHITE:
                        nWhite += 1
                    elif piece == BLACK:
                        nBlack += 1

                if nWhite == 0:
                    value -= weights2[nBlack]
                elif nBlack == 1:
                    value -= weights1[nWhite]

                if nBlack == 4: iswin = True

        self.value = value
        self.iswin = iswin

Don’t worry for now about the details of the weights arrays as I’ll come back to those later and they’re just making lines with different numbers of pieces have different values as discussed earlier. Notice that only lines which are “open”, that is comprising pieces of a single colour and blank squares contribute to the evaluation so in addition to increasing the value because some lines now have more pieces, other lines are no longer open and their contribution to the overall value needs to be removed.

The calculation of the value of a position and whether it is a winning position or not, whilst reasonably efficient now, is still quite computationally expensive. If this was a one off calculation then things wouldn’t be so bad, but as we’ll see, as part of the process of working out which move is best for the computer to play, the same position is going to be seen many times. For now you can see this informally by noticing that even with only three pieces on the board, the same position can often be reached in two different ways. It would be nice if there was an easy way of looking at a position, knowing if it had been seen before and remembering the values from last time it was seen. And that will be the topic of the next post.

In this entry I’ll continue where I left off with game representation and the Board class introduced previously. As it stands the class is pretty limited; it can create an empty board and display it. I’ll now continue implementing the class, providing code to make and undo moves, detect if the game is drawn, and  produce a set of legal moves. I’ll then start to discuss how we might determine if a position is a winning one.

I’m going to dive in and get two of these out of the way quickly; checking for drawn games and generating lists of valid moves. In games like chess both of these can be quite daunting to get right because of the complexity of the game, but the details are very game specific. For Connect 4 they can be written very simply.

    def moveList(self):
        return [ c + 7 * h for c, h in enumerate(self.heights) if h < 6 ]

    def isDraw(self):
        return self.count == 42

The isDraw function is pretty trivial; if the board is full then the game is drawn. Since we’ll be testing this a lot it explains why keeping a count of played pieces earns its keep. The move generator moveList is also very simple; it produces a list of squares where pieces can be played. If a column is full then no piece can be played there, otherwise a piece can be played in the lowest empty square of the column. This explains why we want to keep track of column heights.

The move generator function is integral to games of this sort, but why is it needed? Well when the program needs to choose a move it needs to be able to evaluate positions several moves ahead and to do this it needs to be able to generate those positions by looking at all the available moves from a position and trying them. In chess, producing a list of possible moves can be quite complicated with a lot of special rules like en passant and castling to keep track of. It’s also the case that often the entire set of moves isn’t needed because looking at just a few of the available moves shows all we need to know about how good or bad that chain of moves would be. This means that rather than generate all moves in one go it’s often sensible to have a function that just provides a single move each time it’s called until all moves have been covered or we decide the remaining moves aren’t interesting. If you’re programming in a language like Python that supports generators, this is a good place to use them.

When a human is playing Connect 4 we do not expect them to specify which square on the board they want to play their piece; instead they can specify into which column the piece should drop. For the program however it is easier to specify squares as discussed in the previous entry. The makeMove and undoMove functions therefore take a square as a parameter.

    def makeMove(self, square):
        color = WHITE if self.count & 1 == 0 else BLACK
        self.position[square] = color
        self.heights[square % 7] += 1
        self.count += 1

    def undoMove(self, square):
        self.count -= 1
        self.position[square] = EMPTY
        self.heights[square % 7] -= 1

A quick word of warning is probably needed here. These functions as they stand are far from complete, especially the makeMove function, and will be extended later. However for now they’ll serve to continue the discussion. The only vaguely interesting line in the above is where the makeMove function determines what colour piece to play; even numbered moves are white and odd moves black regardless of which side the human and computer are playing.

Now I want to step back and discuss two things which are more related than at first glance you might think, which incidentally I’ve found to be another trait of game programs in general. How do we determine if a position is a winning one and how do we determine how good or bad any other position is? Take another look at the board.

 35 36 37 38 39 40 41
 28 29 30 31 32 33 34
 21 22 23 24 25 26 27
 14 15 16 17 18 19 20
 07 08 09 10 11 12 13
 00 01 02 03 04 05 06

How would you determine if a position is a winning one? Now how would that change if you knew which side had just played? If you’ve thought it through you should have just halved the amount of work necessary. A naive approach would be to look at every square of the board in turn and then to look at up to three other squares in every direction from that square. If you see a square that is either empty or is not the colour of the piece just played then you can move onto the next direction. As soon as you count 4 squares the same colour you know the position is a winning one and you can stop, but for the vast majority of the time the position won’t be a winning one and you’ll have to look at every direction for every square.

Whilst it will give the correct answer the above approach sucks; it will take a huge amount of time because it is doing an enormous amount of unnecessary work. One good thing that it would provide if implemented correctly would be a way to check that improvements on this scheme are correct. Check your new algorithm gives the same result as the naive one every time it’s called until you have confidence that it’s doing the right thing. I find myself taking this approach a lot when I think I have a new cunning plan to do something quicker; implement the new code but whenever it is called, also make a call to the old, known working code and make sure the two agree. A convenient way of doing this is with assertion statements. I use them a lot.

You could go through a process of improvements improving the algorithm a step at a time. Maybe figure out that if you’re scanning and reach a square that you’ve already scanned from, then you know that can’t be part of a winning line. If you continue in this manner you’ll make a few more improvements and maybe get the running time down to an order of magnitude from the original idea. To make further improvements though sometimes involves throwing away your existing idea and starting again. In that case of course you would want to still use your existing solution to check new approaches are working.

The algorithm outlined above determines lines of four squares on the fly whilst it is trying to find lines of four pieces the same colour. This is similar to how some move generation algorithms work and was used a lot in the past when memory was at a premium. These days however it makes much more sense to precompute such values. In a chess program it’s much more efficient to be able to lookup in a table all the moves a knight might make from a given square than compute it every time. Similarly in our case it’s much more efficient to work out the set of all lines of four squares. For some games this sort of data can be large enough that it makes sense to write another program to generate it for you. With Connect 4 the task isn’t too hard and the data looks like this.

# The set of all lines of 4 squares on a 7 row by 6 column board.

fours = (
    (0, 1, 2, 3), (0, 8, 16, 24), (0, 7, 14, 21),
    (1, 2, 3, 4), (1, 9, 17, 25), (1, 8, 15, 22),
    (2, 3, 4, 5), (2, 10, 18, 26), (2, 9, 16, 23),
    (3, 4, 5, 6), (3, 11, 19, 27), (3, 10, 17, 24), (3, 9, 15, 21),
    (4, 11, 18, 25), (4, 10, 16, 22),
    (5, 12, 19, 26), (5, 11, 17, 23),
    (6, 13, 20, 27), (6, 12, 18, 24),
    (7, 8, 9, 10), (7, 15, 23, 31), (7, 14, 21, 28),
    (8, 9, 10, 11), (8, 16, 24, 32), (8, 15, 22, 29),
    (9, 10, 11, 12), (9, 17, 25, 33), (9, 16, 23, 30),
    (10, 11, 12, 13), (10, 18, 26, 34), (10, 17, 24, 31), (10, 16, 22, 28),
    (11, 18, 25, 32), (11, 17, 23, 29),
    (12, 19, 26, 33), (12, 18, 24, 30),
    (13, 20, 27, 34), (13, 19, 25, 31),
    (14, 15, 16, 17), (14, 22, 30, 38), (14, 21, 28, 35),
    (15, 16, 17, 18), (15, 23, 31, 39), (15, 22, 29, 36),
    (16, 17, 18, 19), (16, 24, 32, 40), (16, 23, 30, 37),
    (17, 18, 19, 20), (17, 25, 33, 41), (17, 24, 31, 38), (17, 23, 29, 35),
    (18, 25, 32, 39), (18, 24, 30, 36),
    (19, 26, 33, 40), (19, 25, 31, 37),
    (20, 27, 34, 41), (20, 26, 32, 38),
    (21, 22, 23, 24),
    (22, 23, 24, 25),
    (23, 24, 25, 26),
    (24, 25, 26, 27),
    (28, 29, 30, 31),
    (29, 30, 31, 32),
    (30, 31, 32, 33),
    (31, 32, 33, 34),
    (35, 36, 37, 38),
    (36, 37, 38, 39),
    (37, 38, 39, 40),
    (38, 39, 40, 41)
)

You can then use this table to examine all possible winning lines without worrying about details like following directions that would take you off the board. The code will be much simpler and faster. Here’s a fairly simple minded implementation of this idea. There is a fairly obvious optimisation to this that I’ll pick up on next time.

    def isWin(self):
        for four in fours:
            piece = self.position[four[0]]

            if piece == EMPTY:
                continue

            for s in four[1:]:
                if self.position[s] != piece:
                    break
            else:
                return True

        return False

Finally, I want to briefly touch on the idea of calculating how good or bad a position is. Code that takes a position and returns a value showing the strength or weakness of that position is called a static evaluation function. It would be useful to have a think about how you might go about implementing this function for Connect 4 and my next entry will mainly discuss my answer to this question.

Recently I’ve been playing around again with my chess program and it occurred to me that it might be useful to try and explain some of the theory and thought processes that go into writing such code. I’m not going to explain how to code chess itself because I suspect I’d soon get dragged down into discussing chess specific details, but instead I’m going to try and touch on problems encountered when writing any similar two player game where both players have complete information; they can both see the board rather than having to guess at what cards an opponent is holding.

To do this I looked around for a game that was complicated enough to be interesting but simple enough not to have too many game specific details. After some thought I decided that Connect 4 would serve this purpose. What I propose to do over the next few articles is to develop the program piece by piece, trying to explain why I make the decisions I do and providing runnable code to illustrate how these ideas are implemented. Although I tend to program mostly in C, for these articles I’ll present the code using Python as it’s much more compact and is easier to follow. Of course I’m assuming that you’re familiar enough with Python that it makes vague sense.

In case anyone is unfamiliar with Connect 4 I’ll summarise the rules here. In its most common form it’s played on a vertical board comprising 7 columns, each of which can hold a stack of up to 6 pieces. The pieces are of different colours, often yellow and red and the players take turns adding a piece of their colour to any column that isn’t yet full. If either player plays a piece that completes a row of four pieces of the same colour, either horizontally, vertically, or diagonally, then they win the game. If the board is full then the game is a draw.

So without further ado I’ll move onto the first interesting subject, that of game representation. The most obvious way of representing the game board is as some sort of array of 7 columns of 6 rows. Each cell in the array can take on one of three different values to represent it being empty or occupied by a piece of either of the two colours. There’s a lot to be said for keeping things simple, but you also have to give some thought as to how easy the board is going to be to manipulate in code and how efficient things like checking for winning positions is going to be.

From experience the code is usually simpler and more efficient if you do away with the idea of an explicit two dimensional array and settle for a flattened representation. For more complicated games like chess the question of efficient board representation becomes much more important and you end up thinking in terms of bitboards. In this game we effectively represent the board as a single dimensional array of length 42 (seven columns by six rows). You can visualise this as each numbered offset within the array corresponding to the position on the board shown below. Python, like most computer languages, considers the first element of an array to have offset zero.

 35 36 37 38 39 40 41
 28 29 30 31 32 33 34
 21 22 23 24 25 26 27
 14 15 16 17 18 19 20
 07 08 09 10 11 12 13
 00 01 02 03 04 05 06

If you think about it, what we’ve described above isn’t really a board but a position on a board. When either side moves it makes a change to the current position to create a new one. Once we start thinking about how the program is going to decide on what moves to make this distinction becomes very important because it will have to effectively make large numbers of moves and then undo them whilst searching for what it considers its best move. This forces us to make a decision; when a move is made do we take a copy of the existing board and make a change to it, or do we just make a change to the board as it stands. If we take the copy then undoing a move is trivial, we just discard the new board and go back to the old one, but if we make changes to the board then we need to remember what moves were made so that they can be undone.

There isn’t really a correct answer to the above question; as usual it’s a trade off. Copying a board involves a lot of memory operations and, if large numbers of positions need examining, potentially quite a large amount of memory. In recent years the amount of memory a program requires has become less of a constraint but at the same time the speed of accessing memory compared with the speed at which modern CPUs operate has become much more noticeable. I’m going to take the easy way out of this and say that from experience my instinct is to use a single board and keep track of how to undo moves as necessary. The other approach would be viable but I suspect efficiency would suffer.

Since there’s going to be a number of operations we’re going to need to perform on game boards it makes sense from a programming point of view to wrap this up into a class. The first cut of the code implementing this class is very simple.

BLACK = -1
EMPTY = 0
WHITE = 1

class Board:
    def __init__(self):
        self.position = [EMPTY for square in range(42)]
        self.heights = [0 for col in range(7)]
        self.count = 0

    def display(self):
        for start in (35, 28, 21, 14, 7, 0):
            for square in [start + i for i in range(7)]:
                c = self.position[square]
                if c == WHITE:
                    k = 'W'
                elif c == BLACK:
                    k = 'B'
                else:
                    k = '_'

                print k,
            print
        print

Wait! What? OK I’ve thrown in a few things here that I need to explain. I’ve been thinking too long in terms of black and white to want to switch now so those are the colours of the pieces we’ll be using, with WHITE moving first. There’s a reason why I want to use -1 for BLACK which I’ll come back to later but for now just accept it as read.

I’ve slipped the heights and count fields in because they’re useful in manipulating the board. The heights field specifies how many pieces are in each column and count is how many pieces have been played so far. The information they hold is redundant in that you could work it out from the position information each time you needed it, but the cost of doing so would outweigh the cost of maintaining it explicitly. This happens a lot in game representations.

The __init__ definition is just Python’s way of specifying what would be a constructor in languages like C++ or Java; a way of creating an instance of the class that it belongs to. In other words, when it’s called it creates a new (empty) board. Don’t worry about the self variable; it’s just there because Python likes to make the fact that class methods take a pointer to the object being acted on explicit.

I’m not going to implement a fancy front end to this code as that’s not what I’m interested in explaining, but it’s useful to be able to look at board positions when checking that code is doing what you expect it to. The display method serves that purpose adequately.

In the next post I’ll continue to discuss board representation and the additional functionality that the Board class will need to provide. Future posts will then move on to moving (ouch), how to decide if a position is good or not and how to get the program to search for a good move.