Possible Search Algorithms for GPUs?

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

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

Re: Possible Search Algorithms for GPUs?

Post by smatovic »

1. heavily restrict the choice of computers that could run the code (or a particular compilation of it)
OpenCL Code is also able to run on CPUs. But you are right with the compilation.
2. interfere with other processes that want to draw on the display (e.g. another window)
Yep, my display freezes during gpu-computation.

--
Srdja
User avatar
marcelk
Posts: 348
Joined: Sat Feb 27, 2010 12:21 am

Re: Possible Search Algorithms for GPUs?

Post by marcelk »

towforce wrote: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)
Sure, but it also opens research on how to scale beyond 160 CPUs or so. It is clear to many that traditional ab-search with iterative deepening, and attempting to parallelize that, got stuck and needs overhaul because of the synchronization bottlenecks. Applications for any resulting algorithms, if found, are not just for GPU, but also CPU clusters, correspondence play (searches with long time controls) and mapping the opening theory efficiently (which is essentially a search with an extremely long time control).
smatovic
Posts: 2641
Joined: Wed Mar 10, 2010 10:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic

Re: Possible Search Algorithms for GPUs? APHID

Post by smatovic »

My YBWC approach on the GPU def failed now, but i found another candidate:

APHID: Asynchronous Parallel Game-Tree Search by Mark G. Brockington and Jonathan Schaeffer

--
Srdja
Daniel Shawul
Posts: 4185
Joined: Tue Mar 14, 2006 11:34 am
Location: Ethiopia

Re: Possible Search Algorithms for GPUs? APHID

Post by Daniel Shawul »

Nope. Aphid is no good performance wise even for cluster search. It keeps the shallow part of the tree in memory to be searched independently by processors. But you still have to use alpha-beta to search each sub-tree. I tried it couple of years ago since it was simple to implement.
Daniel Shawul
Posts: 4185
Joined: Tue Mar 14, 2006 11:34 am
Location: Ethiopia

Re: Possible Search Algorithms for GPUs?

Post by Daniel Shawul »

I just realized the black pawns bit board (bpawns) is completely unnecessary since I let the game go to the very end. It is much faster that way than test if the game has ended prematurely at each ply! So one less bitboard for each thread and saving of some unnecessary work. This game is for a "proof of concept" rather than a real attempt on solving some popular game on gpu.
Dan Andersson
Posts: 442
Joined: Wed Mar 08, 2006 8:54 pm

Re: Possible Search Algorithms for GPUs? APHID

Post by Dan Andersson »

Have to agree with Daniel. APHID has horrible performance characteristics as it scales. Get an AMD GCN card and implement one of the other algorithms.

MvH
smatovic
Posts: 2641
Joined: Wed Mar 10, 2010 10:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic

Re: Possible Search Algorithms for GPUs? APHID

Post by smatovic »

Have to agree with Daniel. APHID has horrible performance characteristics as it scales.
Thanks for the input.
Get an AMD GCN card and implement one of the other algorithms.
I agree, the new AMD GPUs have 3 GB RAM on board, the NV Teslas 6 GB....but the price... :(

--
Srdja
Dan Andersson
Posts: 442
Joined: Wed Mar 08, 2006 8:54 pm

Re: Possible Search Algorithms for GPUs? APHID

Post by Dan Andersson »

The 7770 and 7750 are right around the corner :) They are more reasonably priced.
smatovic
Posts: 2641
Joined: Wed Mar 10, 2010 10:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic

Re: Possible Search Algorithms for GPUs? Cuda - MSCP

Post by smatovic »

@Marcel,

just saw that someone tried to port MSCP to Cuda :)

http://code.google.com/p/cudachess/updates/list

MSCP was a long time a good teacher for me in chess programming, thx for publishing it.

--
Srdja
smatovic
Posts: 2641
Joined: Wed Mar 10, 2010 10:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic

Re: Possible Search Algorithms for GPUs? new gpus

Post by smatovic »

The 7770 and 7750 are right around the corner Smile They are more reasonably priced.
Ah, you are right, according to fudzilla they will be probably released tomorrow, hope they will also be equipped with more than 1 GB ram.

--
Srdja