Creating a Go bot Part II -The board-

 

Note: Lots of this material was taken from my old go blog with some new text that I am adding now because some years passed since that, I am not the same, my coding skills are not the same and my vision and ideas are not the same.

Let’s begin with the development of the bot. First, it needs to understand that there is a go board (goban) and it has positions, but what is the best way to do this?

Long, long time ago there was a document at sensei’s library that I don’t see so, I will copy from my old blog:

Board representation
The most basic of all basics. In order to have a program that can play Go, we need a representation of a Go board in computer terms. Although Go is played on a variety of board sizes, the most popular by far is 19×19. For teaching purposes or for entertainment it also is occasionally played on 13×13 or 9×9. As far as I know, smaller sizes than that are only occasionally used as testing grounds for computer programs. Also boards larger than 19×19 are so rare that I choose to ignore them completely.

For now I will only assume that the board is square so rows == columns, nothing else, the game should be able to be played in any NxN board where N > 0 (well, let’s say N>1, because 1×1 needs to enable suicide move).

Since the board is always square (with an uneven number of lines), common sense would point to using a two-dimensional array to represent the board. Unfortunately computers take much longer to access a two-dimensional array than a one-dimensional array. For this reason most serious Go playing programs will use a one-dimensional array to represent the board. The one-dimensional position z of a board-point x,y is then arrived at by the following conversion: z = x + y *19 (for a 19×19 board represented by a one-dimensional array of size 361). From now on I’ll use xy instead of z as the one-dimensional equivalent of the two-dimensional coordinate x,y. Since the program will internally only use one-dimensional arrays, it will in practice not have to do such conversion often. A computer doesn’t care whether the coordinate is represented in a one dimension or two.

Ok, so as I assumed this board will always be square it follows at some point what I was thinking I should do. For computing pourposes I think it is the same if lines are even or uneven.

Two-dimensional array is a big mistake here, I want to save all the memory I can so I think it is fair to change to a simple array.

There’s a practical difficulty with representing the board in a one dimensional array however. How can the program distinguish between the borders of the board? This is still possible by looking at the coordinate. When xy%19 equals 1 or 19, or when xy/19 equals 1 or 19 we have a point on the 1st line.

I remember when I first red this, I thought that was the end even before starting, but let’s say that after a while I get the idea of how to do this. It seems to be a lot of trouble just to replace a two dimensional array by a simple array, but it is not. Let’s check what’s next:

Next to that is the edge of the board. This is a rather cumbersome way however, and such calculation will cancel out any performance gained by using a one-dimensional representation. The common way to solve this is by usig a bigger array and use border-points around the board to indicate the board boundaries. At first you may think this would lead to a 21×21 representation, and indeed in a two-dimensional board representation this would be the case. When this gets mapped to a one-dimensional array and you’d print out the information stored, you may notice something interesting however. Whenever a border-point is reached to mark the edge of the board, you see two consecutive border-points next to each other. For this reason, the one-dimensional representation can be a little smaller. Instead of 21×21=441 points, we can make do with 20×21+1=421 points. This has one more advantage: to convert a one-dimensional coordinate to two dimensions, the division is by 20 instead of 19 or 21, which is a lot easier for humans. As said before, computers don’t care about such things, but it’s a lot easier when seeing one-dimensional coordinates in your debugger this way. Trust me, it’s a lot easier! After this you should understand the reason behind the constant values defined at the top of the class tesuji.games.go.util.GoArray.

So, you can still imagine a 2 dimensional array using a one-dimensional array, it is just to quit one border x row, because from a row to another you only need one space that will be the border. Something like this:

#########
#*********   <—The next one will be a border.
#*********
#*********
#*********
#*********
#*********
#*********
#*********
#*********
##########

This is just a 9×9 board example, but this would work on any size.

Next point is what I will put in any position of the array, so for our convenience we can use:

  • 0 = empty
  • 1 = black
  • 2 = white
  • 3 = wall
  • 4 = ko

With this I think I am covering all posibilities, if not, I can add more values later.

In my next post I will add more information about this just to not make this post too long. I know this post was a lot about theory, but believe me, next one will show the Python solution for this.

See you then!

Leave a Reply

Your email address will not be published. Required fields are marked *