PV split algorithm

Code, algorithms, languages, construction...
Post Reply
JacobusOpperman
Posts: 6
Joined: Mon Apr 27, 2015 12:35 pm
Real Name: Jacobus Opperman

PV split algorithm

Post by JacobusOpperman » Mon Apr 27, 2015 1:22 pm

Hi
I have written a small chess engine called Alcatraz in Delphi. Recently I have used the pv split algorithm to optimize it for a duo core computer. The parallel searh performs about 40% worse than the serial search and I obviously don't get the 1.8x improvement reported in the literature. I understand the logic behind the pv split algorithm and my program doesn't crash. The way I understand the pv split algorithm is: you search the leftmost branches of the game tree to the horizon depth until you get the principal variation, with one processor, and from thereon the rest of the game tree is searched in parallel with 2 processors. Is it true that you have to create a new thread for most of the nodes of the game tree? My question is: With so many threads running, is the problem not with Windows that it can't deal effectively with the threads and is there not some trick that you can implement to help Windows deal more effectively with all the threads? I am using Windows Vista.
Jacobus Opperman

User923005
Posts: 616
Joined: Thu May 19, 2011 1:35 am

Re: PV split algorithm

Post by User923005 » Tue Apr 28, 2015 12:44 am

If you start more threads than you have physical cores, there will be a terrible drop-off in performance.
With hyperthreading, you can start up to the virtual core count, but it is less efficient than if the processor were not in hyperthreading mode.

JacobusOpperman
Posts: 6
Joined: Mon Apr 27, 2015 12:35 pm
Real Name: Jacobus Opperman

Re: PV split algorithm

Post by JacobusOpperman » Tue Apr 28, 2015 7:53 am

Thank you User923005 for your reply.
Yes I think I create too many threads for too little processors - I basically create a new thread for most of the nodes of the game tree - for everywhere that the game tree splits. I now think I must try to implement the PV split algorithm with only two threads - the main thread and a secondary thread and use global variables to communicate between the two threads.

Post Reply