Efficient parallism

Efficient parallism in Chess is hard. I try different approaches. The multi-window one gives the best results so far.

Beated by the GPU in Chess

Okay, I am not that strong player but I got beaten by my chess chess eninge written in CUDA running on a NVIDIA GeForce 8800 GTX.

I use a few thousands threads together to calculate the best move using multiple windows ( -MATE, -value) (-value, value) ( value, MATE)

Tiny chess engine running

After performing some tests I have a chess engine running as one block on a multiprocessor, using alpha/beta using killer moves as well

Sorting

Also sorting the moves ( captures first) is now done in parallel

Evaluation of a chess position

Evaluation is done with 64 threads to count the value of the pieces

Parallel move generation

One of the advantages of using GPU's multiprocessors. Instead of generation all pseudo legal moves for a given chess position in sequence, I use 64 threads to generate all legal moves parallel!

Alpha beta

Recursion is not possible on the GPU, because the processor on the GeForce 8800 has not stack. Therefore I needed to implement recursion with a state machine and a array which simulates the stackpointer.

TCSP

I used Tom Kerrigan's Simple Chess program as a starting point to test if chess would be possible on a GPU.

First version

The first version is running very inefficient 1000 nodes/s using 1 thread!

Challenge

I started this challenge in january 2007. The challenge is to implement a chess engine purely running on graphical adapters. The idea came after the launch of NVIDIA's CUDA, a SDK to program GPU's.

GPU Chess

Follow the adventure of creating a chess engine on a graphical adapter