| View previous topic :: View next topic |
| Author |
Message |
Srdja Matovic
Joined: 10 Mar 2010
Posts: 310
Location: Hamburg - Germany
|
 Posted: Sat Jan 07, 2012 1:49 pm Post subject: Possible Search Algorithms for GPUs? |
  |
|
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 |
|
| Back to top |
|
 |
Daniel Shawul
Joined: 14 Mar 2006
Posts: 2268
Location: Ethiopia
|
| Posted: Sat Jan 07, 2012 2:29 pm Post subject: 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
| Code: |
__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
_________________
https://sites.google.com/site/dshawul/
https://github.com/dshawul |
|
| Back to top |
|
|
Srdja Matovic
Joined: 10 Mar 2010
Posts: 310
Location: Hamburg - Germany
|
| Posted: Sat Jan 07, 2012 2:56 pm Post subject: Re: Possible Search Algorithms for GPUs? |
|
|
Thank you Daniel for sharing your code, i will take a look at it.
--
Srdja |
|
| Back to top |
|
|
Dan Andersson
Joined: 08 Mar 2006
Posts: 440
|
| Posted: Sat Jan 07, 2012 3:36 pm Post subject: 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. |
|
| Back to top |
|
|
Srdja Matovic
Joined: 10 Mar 2010
Posts: 310
Location: Hamburg - Germany
|
| Posted: Sat Jan 07, 2012 3:54 pm Post subject: Re: Possible Search Algorithms for GPUs? |
|
|
| Quote: |
Two candidates that have some desirable properties:
|
Thank You,
| Quote: |
'Parallel Randomized Best-First Minimax Search' by Yaron Shoham and Sivan Toledo.
|
Sounds good, i will take a closer look.
| Quote: |
'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 |
|
| Back to top |
|
|
Dan Andersson
Joined: 08 Mar 2006
Posts: 440
|
| Posted: Sat Jan 07, 2012 4:28 pm Post subject: Re: Possible Search Algorithms for GPUs? |
|
|
| smatovic wrote: |
| Quote: |
Two candidates that have some desirable properties:
|
Thank You,
| Quote: |
'Parallel Randomized Best-First Minimax Search' by Yaron Shoham and Sivan Toledo.
|
Sounds good, i will take a closer look.
| Quote: |
'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 |
|
| Back to top |
|
|
Srdja Matovic
Joined: 10 Mar 2010
Posts: 310
Location: Hamburg - Germany
|
| Posted: Sat Jan 07, 2012 5:01 pm Post subject: Re: Possible Search Algorithms for GPUs? |
|
|
| Code: |
| 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 |
|
| Back to top |
|
|
Les
Joined: 11 Mar 2006
Posts: 114
Location: NY
|
| Posted: Sun Jan 08, 2012 10:34 pm Post subject: Good Work |
|
|
| 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. |
|
| Back to top |
|
|
Srdja Matovic
Joined: 10 Mar 2010
Posts: 310
Location: Hamburg - Germany
|
| Posted: Fri Feb 10, 2012 12:56 pm Post subject: Re: Possible Search Algorithms for GPUs? |
|
|
| Quote: |
| Quote: |
'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 |
|
| Back to top |
|
|
Paul Gift
Joined: 08 Mar 2006
Posts: 8256
Location: Birmingham UK
|
| Posted: Fri Feb 10, 2012 1:09 pm Post subject: 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)
_________________
"In the land of the blind the one-eyed man is king" - Desiderius Erasmus
"90% of everything is crap" - Sturgeon's Law
The difference between genius and madness is acceptance |
|
| Back to top |
|
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
