Possible Search Algorithms for GPUs?

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
smatovic
Posts: 548
Joined: Wed Mar 10, 2010 9:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic
Contact:

Possible Search Algorithms for GPUs?

Post by smatovic » Sat Jan 07, 2012 1:49 pm

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

Daniel Shawul
Posts: 3561
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Possible Search Algorithms for GPUs?

Post by Daniel Shawul » Sat Jan 07, 2012 2:29 pm

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&#40;int i = 0;i < N;i++) &#123;
		wpawns = wpawns_;
		bpawns = bpawns_;
		all = all_;
		player = player_;
		emptyc = emptyc_;

		while&#40;emptyc&#41; &#123;
			randn *= 1103515245;
			randn += 12345;

			U32 rbit = randn % emptyc;
			U64 mbit = all;
			for&#40;U32 i = 0;i < rbit;i++)
				mbit &= mbit - 1; 
			mbit = mbit & -mbit;

			if&#40;player == 0&#41;
				wpawns ^= mbit;
			else
				bpawns ^= mbit;
			all ^= mbit;
			player ^= 1;
			emptyc--;
		&#125;

		U64 m = &#40;wpawns & UINT64&#40;0x00000000000000ff&#41;),oldm;
		do &#123;
			oldm = m;
			m |=(((&#40;m << 8&#41; | &#40;m >> 8&#41;) | 
				 ((&#40;m << 9&#41; | &#40;m << 1&#41;) & UINT64&#40;0xfefefefefefefefe&#41;) | 
				 ((&#40;m >> 9&#41; | &#40;m >> 1&#41;) & UINT64&#40;0x7f7f7f7f7f7f7f7f&#41;)) 
				 & wpawns
				);
			if&#40;m & UINT64&#40;0xff00000000000000&#41;) &#123;
				wins++;
				break;
			&#125;
		&#125; while&#40;m != oldm&#41;;

	&#125;
	return wins;
&#125;
You can download the full source code here

regards,
Daniel

smatovic
Posts: 548
Joined: Wed Mar 10, 2010 9:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic
Contact:

Re: Possible Search Algorithms for GPUs?

Post by smatovic » Sat Jan 07, 2012 2:56 pm

Thank you Daniel for sharing your code, i will take a look at it.

--
Srdja

Dan Andersson
Posts: 442
Joined: Wed Mar 08, 2006 7:54 pm

Re: Possible Search Algorithms for GPUs?

Post by Dan Andersson » Sat Jan 07, 2012 3:36 pm

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.

smatovic
Posts: 548
Joined: Wed Mar 10, 2010 9:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic
Contact:

Re: Possible Search Algorithms for GPUs?

Post by smatovic » Sat Jan 07, 2012 3:54 pm

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

Dan Andersson
Posts: 442
Joined: Wed Mar 08, 2006 7:54 pm

Re: Possible Search Algorithms for GPUs?

Post by Dan Andersson » Sat Jan 07, 2012 4:28 pm

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

smatovic
Posts: 548
Joined: Wed Mar 10, 2010 9:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic
Contact:

Re: Possible Search Algorithms for GPUs?

Post by smatovic » Sat Jan 07, 2012 5:01 pm

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

vb4
Posts: 149
Joined: Sat Mar 11, 2006 4:45 am
Location: NY

Good Work

Post by vb4 » Sun Jan 08, 2012 10:34 pm

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.

smatovic
Posts: 548
Joined: Wed Mar 10, 2010 9:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic
Contact:

Re: Possible Search Algorithms for GPUs?

Post by smatovic » Fri Feb 10, 2012 12:56 pm

'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

User avatar
towforce
Posts: 9174
Joined: Wed Mar 08, 2006 11:57 pm
Location: Birmingham UK

Re: Possible Search Algorithms for GPUs?

Post by towforce » Fri Feb 10, 2012 1:09 pm

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)
"free speech requires rules to filter the functional from the dysfunctional" - link
Expect nothing. Appreciate everything!

Post Reply