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
Possible Search Algorithms for GPUs?
Moderators: hgm, Rebel, chrisw
-
- Posts: 2662
- Joined: Wed Mar 10, 2010 10:18 pm
- Location: Hamburg, Germany
- Full name: Srdja Matovic
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Possible Search Algorithms for GPUs?
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
You can download the full source code here
regards,
Daniel
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;
}
regards,
Daniel
-
- Posts: 2662
- Joined: Wed Mar 10, 2010 10:18 pm
- Location: Hamburg, Germany
- Full name: Srdja Matovic
Re: Possible Search Algorithms for GPUs?
Thank you Daniel for sharing your code, i will take a look at it.
--
Srdja
--
Srdja
-
- Posts: 442
- Joined: Wed Mar 08, 2006 8:54 pm
Re: Possible Search Algorithms for GPUs?
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.
'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.
-
- Posts: 2662
- Joined: Wed Mar 10, 2010 10:18 pm
- Location: Hamburg, Germany
- Full name: Srdja Matovic
Re: Possible Search Algorithms for GPUs?
Thank You,Two candidates that have some desirable properties:
Sounds good, i will take a closer look.'Parallel Randomized Best-First Minimax Search' by Yaron Shoham and Sivan Toledo.
I already tried a simplified Nagging approach with less communication, the nodecount was smaller but not that much.'Nagging: A Scalable Fault-Tolerant Paradigm for Distributed Search' and other Nagging papers by Alberto Maria Segre.
--
Srdja
-
- Posts: 442
- Joined: Wed Mar 08, 2006 8:54 pm
Re: Possible Search Algorithms for GPUs?
Sounds interesting with the simplified Nagging. Aside from the reduced nodecount did it impact/improve play any?smatovic wrote:Thank You,Two candidates that have some desirable properties:
Sounds good, i will take a closer look.'Parallel Randomized Best-First Minimax Search' by Yaron Shoham and Sivan Toledo.
I already tried a simplified Nagging approach with less communication, the nodecount was smaller but not that much.'Nagging: A Scalable Fault-Tolerant Paradigm for Distributed Search' and other Nagging papers by Alberto Maria Segre.
--
Srdja
MvH Dan Andersson
-
- Posts: 2662
- Joined: Wed Mar 10, 2010 10:18 pm
- Location: Hamburg, Germany
- Full name: Srdja Matovic
Re: Possible Search Algorithms for GPUs?
Code: Select all
Sounds interesting with the simplified Nagging. Aside from the reduced nodecount did it impact/improve play any?
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
-
- Posts: 2662
- Joined: Wed Mar 10, 2010 10:18 pm
- Location: Hamburg, Germany
- Full name: Srdja Matovic
Re: Possible Search Algorithms for GPUs?
Hmm, the algorithm sounds promising but i have some doubtsSounds good, i will take a closer look.'Parallel Randomized Best-First Minimax Search' by Yaron Shoham and Sivan Toledo.
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
-
- Posts: 11589
- Joined: Thu Mar 09, 2006 12:57 am
- Location: Birmingham UK
Re: Possible Search Algorithms for GPUs?
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)
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)
Writing is the antidote to confusion.
It's not "how smart you are", it's "how are you smart".
Your brain doesn't work the way you want, so train it!
It's not "how smart you are", it's "how are you smart".
Your brain doesn't work the way you want, so train it!