Page 1 of 3
Possible Search Algorithms for GPUs?
Posted: Sat Jan 07, 2012 2:49 pm
by smatovic
hi,
last time i asked for an possible Board Presentation and Move Generation suited for GPUs,
these two topics are solved by use of Quad-Bitboards and a Magic Bitboard Move Generator (thanks to Gerd Isenberg and the Stockfish Team).
Now its up on the Search Algorithm which is required to feed thousands of threads.
Monte Carlo Tree Search would be easy to implement, but my simple implementation on a cpu shows random game play without any statistical significance. UCT may be a way to improve the results, but i don't think that this is an easy part to port on the GPU.
Parallel AlphaBeta Search like YBWC or DTS need, from GPU-view, sophisticated ways for communication and i am not sure how they will perform with thousands of threads.
Plain MiniMax could be another option to get chess running on a gpu, but i am not sure how to distribute work across threads. A Elimination Backoff Stack could be a solution...
Looking for some ideas or inspiration,
Srdja
Re: Possible Search Algorithms for GPUs?
Posted: Sat Jan 07, 2012 3:29 pm
by Daniel Shawul
Hello Srdja
I was working on a Hex game using CUDA some time ago. I dud the monte-carlo simulations on gpu and that is it. The game winning condition is to make a line (horizontal/vertical) which I implemented using some bitboard trick I got from here. Anyway since you are looking for inspiration, I though I will cheap in. Here is the source code
Code: Select all
__device__
int BOARD::playout(int N) {
__shared__ U64 wpawns_;
__shared__ U64 bpawns_;
__shared__ U64 all_;
__shared__ char player_;
__shared__ char emptyc_;
wpawns_ = wpawns;
bpawns_ = bpawns;
all_ = all;
player_ = player;
emptyc_ = emptyc;
int wins = 0;
for(int i = 0;i < N;i++) {
wpawns = wpawns_;
bpawns = bpawns_;
all = all_;
player = player_;
emptyc = emptyc_;
while(emptyc) {
randn *= 1103515245;
randn += 12345;
U32 rbit = randn % emptyc;
U64 mbit = all;
for(U32 i = 0;i < rbit;i++)
mbit &= mbit - 1;
mbit = mbit & -mbit;
if(player == 0)
wpawns ^= mbit;
else
bpawns ^= mbit;
all ^= mbit;
player ^= 1;
emptyc--;
}
U64 m = (wpawns & UINT64(0x00000000000000ff)),oldm;
do {
oldm = m;
m |=((((m << 8) | (m >> 8)) |
(((m << 9) | (m << 1)) & UINT64(0xfefefefefefefefe)) |
(((m >> 9) | (m >> 1)) & UINT64(0x7f7f7f7f7f7f7f7f)))
& wpawns
);
if(m & UINT64(0xff00000000000000)) {
wins++;
break;
}
} while(m != oldm);
}
return wins;
}
You can download the full source code
here
regards,
Daniel
Re: Possible Search Algorithms for GPUs?
Posted: Sat Jan 07, 2012 3:56 pm
by smatovic
Thank you Daniel for sharing your code, i will take a look at it.
--
Srdja
Re: Possible Search Algorithms for GPUs?
Posted: Sat Jan 07, 2012 4:36 pm
by Dan Andersson
Two candidates that have some desirable properties:
'Parallel Randomized Best-First Minimax Search' by Yaron Shoham and Sivan Toledo.
'Nagging: A Scalable Fault-Tolerant Paradigm for Distributed Search' and other Nagging papers by Alberto Maria Segre.
Re: Possible Search Algorithms for GPUs?
Posted: Sat Jan 07, 2012 4:54 pm
by smatovic
Two candidates that have some desirable properties:
Thank You,
'Parallel Randomized Best-First Minimax Search' by Yaron Shoham and Sivan Toledo.
Sounds good, i will take a closer look.
'Nagging: A Scalable Fault-Tolerant Paradigm for Distributed Search' and other Nagging papers by Alberto Maria Segre.
I already tried a simplified Nagging approach with less communication, the nodecount was smaller but not that much.
--
Srdja
Re: Possible Search Algorithms for GPUs?
Posted: Sat Jan 07, 2012 5:28 pm
by Dan Andersson
smatovic wrote:Two candidates that have some desirable properties:
Thank You,
'Parallel Randomized Best-First Minimax Search' by Yaron Shoham and Sivan Toledo.
Sounds good, i will take a closer look.
'Nagging: A Scalable Fault-Tolerant Paradigm for Distributed Search' and other Nagging papers by Alberto Maria Segre.
I already tried a simplified Nagging approach with less communication, the nodecount was smaller but not that much.
--
Srdja
Sounds interesting with the simplified Nagging. Aside from the reduced nodecount did it impact/improve play any?
MvH Dan Andersson
Re: Possible Search Algorithms for GPUs?
Posted: Sat Jan 07, 2012 6:01 pm
by smatovic
Code: Select all
Sounds interesting with the simplified Nagging. Aside from the reduced nodecount did it impact/improve play any?
Only by decreasing the search time a bit for a fixed depth search.
I simply ran simultanous threads on the same chess position from a stacklist witth a narrowed alpha-beta window.
The complete "Nagging - SPAM" algorithm is described in this paper:
http://jmvidal.cse.sc.edu/library/segre02a.pdf
--
Srdja
Good Work
Posted: Sun Jan 08, 2012 11:34 pm
by vb4
Nice going, this is what will take us to doing good research work in the field of chess! No bickering just some help which we all can make contributions if we did more work and less debates.
Re: Possible Search Algorithms for GPUs?
Posted: Fri Feb 10, 2012 1:56 pm
by smatovic
'Parallel Randomized Best-First Minimax Search' by Yaron Shoham and Sivan Toledo.
Sounds good, i will take a closer look.
Hmm, the algorithm sounds promising but i have some doubts
1) it keeps the search tree in memory
2) for chess they implemented a 3 ply search at leaf nodes by using Crafty as a Blackbox.
3) they've tested only 35 processors...i intend to use 512 to 2048 threads.
...my last YBWC apporach failed due to spinlocks, so i think i will give it anyhow a try.
Thanks again for posting,
Srdja
Re: Possible Search Algorithms for GPUs?
Posted: Fri Feb 10, 2012 2:09 pm
by towforce
Wouldn't doing chess engine work on the GPU:
1. heavily restrict the choice of computers that could run the code (or a particular compilation of it)
2. interfere with other processes that want to draw on the display (e.g. another window)