TalkChess.com

[Daniel Shawul]

I have finally finished a uct for chess on gpu. It is not that it is difficult but that move generation and other stuff consume space. Go would be ideal for UCT but requirement of linked list of stones for capture detection is a performance killer. Checkers would be another game ideally suited for gpu if i manage to generate those captures ...
It turned out to be a lot more slower than Hex since move generation and legality testing is a pain in the neck. The most annoying thing is that
there is not enough space to declare an int[256] for each thread to hold on the moves generated.
Bear in mind it is not a stack but just one entry. Here are the callenges:

a) The move generation step I mentioned above. I have gone through great length to generate one legal random move:
1 - Count pseudo legal moves
2 - generate a random number and pick which move to test
3 - generate only that move
4 - make the move and test for legality
5 - keep a bitset of 256 bits to mark moves that are already tested. This added 7 more registers (total = 59 now)
6 - If all bits are set as is the case when checkmated, break out.
I use kindergarten bitboards (8 bitboards total) which are light weight (512bytes for bishop/rook attacks).
But legal move generation is a pain due to either big table requirement in_between, direction[64][64] etc..
or something else. If I can generate a random legal move, it would save me from going through all those trouble.

b) Due to high register pressure (almost 60 right now), the occupancy is very low. Only 17% at my GPU right now.
But it is still 2-3x faster. I can offload some of those to shared memory but it is debatable whether trying to increase
occupancy that way is better. Some guys who did FFT using cuda claim that lower occupancy with high register usage actually
runs faster. Also the nvcc optimizer is very good so trying to squeeze out a register or two takes a lot of effort!

b) I use a copy / make instead of do / undo basically because there is n't space for a stack. But to test for legality
of pseudo legal moves I needed to save enpassant,castle,fifty,player flags just for one step. So undo is used there.
For the rest of MC playout a copy/make is used. BTW the 8 bitboards for positions representation simplifies do/undo and
my undo_move is basically do_move itself. A little problem I encounted with that board representation is that it is difficult
/slower to know what kind of piece is being captured. I delay that detection until I actually make the move ..

c) 32 bit firstone and bitcounts are ok but still very slow. I need to count psedudo legal moves before generating them.
The bitboards are very sparse and maybe a simpler version of population count would help.

e) Can't use arrays if you want your variable to be stored on register. Could be a pain for coding with many switch staments needed.

Probably some more. Ideas are welcome especially on how to generate legal random moves for chess preferable without using
large tables.

I guess that if I modify the uct code a bit it would be a fast UCT_perft approximator.

---
cheers
_________________
https://sites.google.com/site/dshawul/
https://github.com/dshawul