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 representationSo, 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).

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.

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

## No comments:

## Post a Comment