Sunday, April 20, 2008

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.

3 comments:

Thomas DA said...

Even if you succeed in making a "recursive" search, I think you'll have a hard time in turning it into alphabeta, which requires knowledge of previous searched moves.

Hieronymus said...

Yes, parallelization of alpha beta is not efficient. Well I succeeded in making a recursive search using a simulated stack.

Thomas DA said...

I'd like to see a state diagram for such a machine.

As you probably know there has been a lot of work into making multiple threads run alphabeta: http://www.cis.uab.edu/info/faculty/hyatt/search.html (which is a part of Dr. Robert Hyatt excellent chess page: http://www.cis.uab.edu/info/faculty/hyatt/pubs.html )

I don't know if it is useable with as many threads as you've got on the cpu though. On the other hand - the number of nodes is still much much larger than the number of threads, so perhaps.