Day 1: Board representation.

First of all, I have to thank a lot to the Computer Go mailing list, so if you are interested in computer go, suscribe to it here. I asked them for some papers and information for beginners information and they answered me with very interesting information.

The first document that I am reading is the one about board representation on Senseis. It is very interesting, so I will divide the text and comment my impressions and conclutions. If the owners of the wiki don't want this text copied please tell me and I will quit it.

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 payed on a variety of board sizes, the most popular by far is 19x19. For teaching purposes or for entertainment it also is occasionally played on 13x13 or 9x9. As far as I know, smaller sizes than that are only occasionally used as testing grounds for computer programs. Also boards larger than 19x19 are so rare that I choose to ignore them completely.

So, I think I will try to implement a dynamic array limited by a number  of rows and cols (in theory both are equal, but it should be possible to change it).

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 19x19 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.

• So, the board will be a square (rows=cols), that's good.
• One dimension array? Ok, this will be more difficult, but... 

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.

 Now, there is a good explanation. I will need to create a method to convert from a 2 coordinates position to a 1 coordinate position.

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 21x21 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 21x21=441 points, we can make do with 20x21+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, let's see if I understand, when I reach the border in one side the next one will be a border to, so I don't need to tell there is a border. For example something like this (let's say a 9x9 board):

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

OK, this is initially about the Go board. The Go board has all the information there is, still it's rather limited for a computer program to do anything useful. A Go board has points that can only be in one of three states: empty, a black stone or a white stone. So that's all that the array will contain. 

Well I can go with an integer, for example 1=black, 2=white, 3=not playable

This will be hard... very hard