Possible Search Algorithms for GPUs?

[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

[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&#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]

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

--
Srdja

[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.

[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

[Dan Andersson]

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]

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]

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]

'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

[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)