Possible Search Algorithms for GPUs?

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
smatovic
Posts: 909
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 1:33 pm

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: Fri Feb 26, 2010 11:21 pm
Contact:

Re: Possible Search Algorithms for GPUs?

Post by marcelk » Sun Feb 12, 2012 10:49 am

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: 909
Joined: Wed Mar 10, 2010 9:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic
Contact:

Re: Possible Search Algorithms for GPUs? APHID

Post by smatovic » Sun Feb 12, 2012 9:29 pm

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: 3758
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Possible Search Algorithms for GPUs? APHID

Post by Daniel Shawul » Sun Feb 12, 2012 10:00 pm

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: 3758
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Possible Search Algorithms for GPUs?

Post by Daniel Shawul » Mon Feb 13, 2012 4:00 pm

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 7:54 pm

Re: Possible Search Algorithms for GPUs? APHID

Post by Dan Andersson » Mon Feb 13, 2012 6:14 pm

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: 909
Joined: Wed Mar 10, 2010 9:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic
Contact:

Re: Possible Search Algorithms for GPUs? APHID

Post by smatovic » Mon Feb 13, 2012 9:24 pm

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 7:54 pm

Re: Possible Search Algorithms for GPUs? APHID

Post by Dan Andersson » Tue Feb 14, 2012 10:29 am

The 7770 and 7750 are right around the corner :) They are more reasonably priced.

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

Re: Possible Search Algorithms for GPUs? Cuda - MSCP

Post by smatovic » Tue Feb 14, 2012 11:52 am

@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: 909
Joined: Wed Mar 10, 2010 9:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic
Contact:

Re: Possible Search Algorithms for GPUs? new gpus

Post by smatovic » Tue Feb 14, 2012 12:40 pm

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

Post Reply