sabato 30 novembre 2013

A modern way to collect Principal Variation

While following some discussion in the past months on talkchess about collecting PV I decided that I want my engine to collect the true Principal Variation while searching the tree.
Some other engines doesn't collect the true Principal Variation and try to reconstruct it , with good results most of the times, from the transposition table.

But first of all, what is the Principal Variation (PV from now)?
If you look at the definition given from chessprogramming wiki it's "a sequence of moves that programs consider best and therefore expect to be played."
It's collected to print it and show what the engine think it's the best line and not less important it's used in iterative deepening to choose how to order moves.

Look at the following example:
white to move 1. Ne5!



When after some time the engine end the search at depth 4 and collect a PV that may look like Ne5 Dd8 Nxg6 fxg6 and start a search at depth 5 , it's better to start the new search searching the line 1.Ne5 Dd8 2.Nxg6 fxg6 3.a4 than the line 1. Kh1 Kh8 2.Kg1 Kg8 3. Kh1 which hardly will be the new PV.


Now that we had defined what is a PV line and what we need to collect it let's look HOW to collect it in a very modern way.

Collecting PV with C++11

a very clean way to collect PV with C++11 is by using std::vector. It will accept any lenght PV lines.

1:  #include <vector>  
2:  #include <algorithm>  // std::copy  
3:  #include <iterator>   // std::back_inserter  
4:    
5:  void think(){  
6:    
7:   std::vector<Move> newPV;  
8:    
9:    
10:   //.........  
11:   // inside iterative deepening framework  
12:     
13:   newPV.clear();  
14:   // search and collect newPV  
15:   res=alphaBeta(0,position,depth,alpha,beta,newPV);  
16:     
17:   // display PV  
18:   for (auto & m :newPV){  
19:    std::cout<<position.displayUci(m)<<" ";  
20:   }  
21:    
22:    
23:   //......  
24:  }  
25:    
26:  Score alphaBeta(unsigned int ply,Position & pos,int depth,Score alpha,Score beta,std::vector<Move>& PV){  
27:   //.....  
28:   generate_legal_moves();  
29:   for(each legal move){  
30:    std::vector<Move> childPV;  
31:    doMove(m)  
32:    val=-alphaBeta(ply+1,pos,depth-ONE_PLY,-beta,-alpha,childPV);  
33:    undoMove(m);  
34:    
35:    if(val>alpha && val <beta){  
36:     bestMove=m;  
37:     alpha =val;  
38:    
39:     PV.clear();  
40:     PV.push_back(bestMove);  
41:     std::copy(childPV.begin(),childPV.end(),back_inserter(PV));  
42:    }  
43:   }  
44:  }  

From line 39 to 41 you can see how each time you find a new best move in the alpha beta search you save the move as BESTMOVE and fill the PV of the node with the best move followed by the child node PV.

From line 13 to 19 you can see how inside the iterative deepening framework you can retrieve the new PV and display it in a very easy and clean way.
I really like C++.

what about performance?

std::vector is not the fastest way to implement PV collecting, probably a triangular PV table or collecting it by transposition table will be faster, but using std::vector you don't need to fear for PV lenght because std::vector will automatically grow to accept "any" PV lenght.
another thing to consider is that you only have to save a new PV very few times in a search.
Just to post an example if I let my engine search the WAC position 2 ( fen
8/7p/5k2/5p2/p1p2P2/Pr1pPK2/1P1R3P/8 b - - ) up do depth 17 I get only 20 million alpha raising over 381 million node tested, near 6 percent but my move ordering is still very very bad

1 commento:

  1. Hi I use C# so am not familiar with back_inserter(), what does it do?

    RispondiElimina