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  
5:  void think(){  
7:   std::vector<Move> newPV;  
10:   //.........  
11:   // inside iterative deepening framework  
13:   newPV.clear();  
14:   // search and collect newPV  
15:   res=alphaBeta(0,position,depth,alpha,beta,newPV);  
17:   // display PV  
18:   for (auto & m :newPV){  
19:    std::cout<<position.displayUci(m)<<" ";  
20:   }  
23:   //......  
24:  }  
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);  
35:    if(val>alpha && val <beta){  
36:     bestMove=m;  
37:     alpha =val;  
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

lunedì 25 novembre 2013

first achievement: MOVE GENERATOR

Vajolet rebuilding continue with good results, today I (probably) have a bug free move generator!

these are the tech spec of the engine:
  • bitboard move generator with piecelist to help the generation
  • full legal move generator ( I don't like pseudolegal one)
  • working in both linux/windows environment
  • full working perft/divide function
  • 32 bit tested code (I still lack a 64 bit test setup)
  • faster than Vajolet 2.03 generator (36Mnodes/s on a 2 years old machine)
but how can we can test the move generator is good and free of bug?

The answer is the use of the perft function. The first thing to do is test the engine against the positions on this page; when I was satisfied with the results I tested my engine against a bigger testsuite verifying the correctness of the result with stockfish.

The last thing that I have done is implementing a uci "go" command that return as bestmove a random move from the legalMove list and make the engine play against himself for some hours with the cutechess-cli program and check at the end that there are no game ended because of an "illegal" move.

giovedì 21 novembre 2013

Vajolet chess engine

After a year of hard work, my engine Vajolet, reached a level that make me proud of it but now I feel like it need to be rewritten from scratch to solve some design problem that stop it from reaise to the 3000 elo points.

My engine has just reached the 2650 elo point in CCRL 40/40 list and the 67th position and a new version is ready to be release. This will be the last release of Vajolet as you know it. In the last year, following the winglet blog and then studying lots of free engine like stockfish, cheng and fruit I was able to write a good engine.

Now I have hit some stonewall made of past design choice that make me make no progress at all so I decided to restart th project, taking all the good things of the old code, discard some idea and try to build a better engine.

but what are the main problems of vajolet?

  • a design that make very difficult to add multithread
  • a code that can only work on windows
  • poor testing 

so what's are my new GOAL for the new code? 

  • first of all a multithread engine ( it will be added only when the engine will be in an advanced state of developing)
  • 32/64 bit compile and use of SSE parallel instruction for the evalutation.
  • a full working windows/ linux environment
  • c++11 to use some very interesting new feature and libraries like the new randomMersenne twister and portable threading library.
  • a good framework to test, evalutate and rank my engine.
  • bug free code. I need more test and lots of assert and deterministic code (I'll check vajolet result with more than one compiler in debug and release compile).

what have I achieved up to now?

up to now I have rewritten the legal move generator, the code to check that a move is legal, the make/unmake code and the UCI parser.
The new code runs nicely on both windows 7 and linux and is fast as the old one. I still havent tried the code on a 64 bit platform but I'll do as soon as possibile.

what I need to do now?

I need to finish testing my legal move generator, document it, add lot of assert and as soon as I get satisfied from this code I'll go to the next task:  start to write a simple alpha/beta searcher.

I also decided tos tart this blog to keep you informed about my progress and to release/explain my testing/developing procedure.

sincerely yours Marco Belli