> For example, something I suggested the last time I was on a computer go > list, back in the 90's: Take an array of 7 64-bit integers...
I believe very similar techniques are pretty common - I don't know how common but it's been used before. I believe you might as well just use use bit-boards - where one color is represented as a single large integer. For a large board such as 19x19 (or even 9x9) you have to fake it, building your own routines or using a bignum library to do the shifts and other logical operations - but it's still very fast for many operations. Shifting is a bit of a bottleneck but on a 64 bit computer you are doing a lot of work in parallel with a 64 bit shift. One good thing about this is most operations do not require conditional branching which can be a killer to modern processors when it's not easy to predict which direction the branch will go. I don't keep up with this much these days - perhaps the state of the art has improved? I did such a move generator in a high level language. It's very tiny, as the code to make and test a move are just a few logical operators. So the code to do this is very clean and compact and is quickly debugged. It's a little inconvenient to decode a bit board - for instance if you have a bit board representing all the legal moves and you wish to grab them one at a time inside a loop, then you need an efficient routine for finding an arbitrary bit. Some processors have an instruction built into them to do this - something to find the left-most or right-most bit set (it's often cast as a problem of counting how many zero bits on the left or right, but it's the same thing.) I'm not sure the instruction is always fast however. There are lots of interesting ways to construct such a routine but it becomes even more elaborate when you have artifically long integers - you must do this 1 piece at a time. Still, I have long considered writing a program this way - just to see for myself if it can be made fast. Some chess programs use the technique to advantage, even on 32 bit computers even though it's faster and more natural on 64 bit computers for Chess. You shold go ahead a build an engine using your ideas. As a group we have developed an almost standardized performance test - see how fast you can generate uniformly random moves by playing a few thousand random games. Compare it with the numbers that have been posted on this group. Your idea is useful if it can be show to be superior in some way to other move generation techniques. It may be superior in speed or some other metric. - Don On Sun, 2007-03-25 at 18:55 +0000, forrest curo wrote: > Since I signed up for this list, I've been receiving all sorts of > material about how to test existing programs against one another. > > Does this bunch ever get around to the merits of various ways of > representing the board and arriving at moves? > > For example, something I suggested the last time I was on a computer go > list, back in the 90's: Take an array of 7 64-bit integers... > > Put the top row of the board into bits 58-40 of the second integer, the > next row into the same part of the third integer, so-on until the 7th > row fits into bits 38-20 of the first integer (and the 14th into bits > 19-1.) Bits 59-40 of the first integer, 18-0 of the 7th integer, are > zeroed out (representing rows off the top and the bottom of the board, > respectively.) > > If we're showing the spaces on a vacant board, for example, that's > > $00000ffffeffffe nothing -row 7-row 14 > $ffffeffffeffffe row 1--row 8--row 15 > $ffffeffffeffffe row 2--row 9--row 16 > $ffffeffffeffffe row 3--row 10--row 17 > $ffffeffffeffffe row 4--row 11--row 18 > $ffffeffffeffffe row 5--row 12--row 19 > $ffffeffffe00000 row 6--row 13--nothing > > Seven large numbers showing the presence or absence of one condition > (in this case, an empty intersection) at each point. > > Not useful? If you have an array like this, and another like it showing > the location of all the black spaces, a few shifts and bitwise logical > operations will give you a new array showing all the breathing spaces of > all black chains on the board. > > It takes at least two such arrays to fully represent a go position, with > considerable redundancy at that, even more so if you use separate arrays > for black stones, white stones, empties--but on a true 64-bit machine, > one ought to be able to test for all sorts of local configurations > really FAST. > > Even on the plain old 32 bit pc I was using back when I actually worked > on this, I found the representation above was good for quickly detecting > captures (etc). These days, considering trying again, still on 32 bits, > I'm inclined to use 19-integer arrays for the sake of keeping things > simple & debuggable. But maybe someone else will find a use for this > system--or suggest an arrangement I might find more useful? > > Forrest Curo > San Diego > _______________________________________________ > computer-go mailing list > [email protected] > http://www.computer-go.org/mailman/listinfo/computer-go/ _______________________________________________ computer-go mailing list [email protected] http://www.computer-go.org/mailman/listinfo/computer-go/
