This is my first question on the forum, so I hope not to break any rule.
For the past 3 months, I have been binge-developing a chess engine in c++, following some tutorials and reading a lot from chessprogramming.org as well as from http://www.frayn.net/beowulf/ and this forum. Now I have implemented lot of stuff starting from the most basic stuff (pvs with alpha beta + null move + LMR + TT , move ordering with history/counter/killer moves heuristic, MVVLVA, IID and move from tt).
Now I've got to say that I am proud of the engine, but at the same time I felt like something was kinda "off" about the way the engine performed.
So I decided to write some code to profile two of the most vital parts of the engine: move ordering and transposition table.
As for the move ordering, what I did was:
- I have a variable nodesWithMoves = 0, that gets increased each time a node with one or move legal moves is encountered in the search (it ignores the nodes that are cut with NMP, as the move generation only occours after NMP).
- I have an array moveCorrectAt[128], that keeps track of the position of the best/cut move for each node analyzed, for example if the best move was the fifth to be generated, then moveCorrectAt[4] would be increased.
- Finally, I would print for each depth division moveCorrectAt/nodesWithMoves, for each i from 0 to 128 (excluded).
As for the TT, i am using a simple (and probably very unoptimized) structure:
Code: Select all
struct tt {
U64 key = 0; //the complete key
char depth = 0; //the complete depth
char flags = 0; //can be either hashALPHA, hashBETA, hashEXACT
int score = 0; //the score assigned to the position
int move = 0; //the best/cut move in the position (move has 40 bit ordering score and 24 bit move, and we don't need to store the move score, so we cut away the score int the writeHashEntry and store it as an int)
inline void wipe(); //resets all members to 0
};
Code: Select all
inline void writeHashEntry(U64 key, int score, int depth, moveInt move, int hashFlag) {
//...
if (depth < hash_entry->depth || (depth == hash_entry->depth && hashFlag != hashEXACT && hash_entry->flags == hashEXACT )) return; //don't replace
//...
};
Code: Select all
inline int readHashEntry(U64 key, int alpha, int beta, int depth) {
tableAccesses++;
//...
if (hashEntry->key == key) {
tableHits++;
//...
}
//...
}
Now the results:
As for the move ordering, i tested startpos up to depth 24, which yielded these results (only displaying first 10 moves each 8 depths):
Code: Select all
Move guessRate @depth 8:
1 --> Perc: 0.0924519
2 --> Perc: 48.5415
3 --> Perc: 12.1404
4 --> Perc: 5.70164
5 --> Perc: 3.09044
6 --> Perc: 1.51303
7 --> Perc: 0.878873
8 --> Perc: 0.636583
9 --> Perc: 0.507398
10 --> Perc: 0.501499
Move guessRate @depth 16:
1 --> Perc: 0.0954534
2 --> Perc: 48.8485
3 --> Perc: 12.2974
4 --> Perc: 5.76588
5 --> Perc: 3.10437
6 --> Perc: 1.51738
7 --> Perc: 0.880836
8 --> Perc: 0.636266
9 --> Perc: 0.506761
10 --> Perc: 0.49833
Move guessRate @depth 24:
1 --> Perc: 0.155728
2 --> Perc: 62.7145
3 --> Perc: 14.8752
4 --> Perc: 6.29885
5 --> Perc: 3.0888
6 --> Perc: 1.44694
7 --> Perc: 0.814006
8 --> Perc: 0.575404
9 --> Perc: 0.462268
10 --> Perc: 0.420881
I was kinda happy with the results, because there definitely is an ascending trend in the accuracy, but at the same time I don't know what a good move ordering percentage should be, so I was hoping that some of you who also tested this stuff could give me some expected numbers.
But then on to the hit rate, using an hashtable of 16777216 (0x1000000) ttEntries.
It was...
Code: Select all
@depth 8 hitrate 4.02875%
@depth 9 hitrate 3.6063%
@depth 10 hitrate 3.6706%
@depth 11 hitrate 3.26097%
@depth 12 hitrate 3.39939%
@depth 13 hitrate 3.77532%
@depth 14 hitrate 3.68911%
@depth 15 hitrate 4.0221%
@depth 16 hitrate 4.11454%
@depth 17 hitrate 4.05831%
@depth 18 hitrate 3.59045%
@depth 19 hitrate 3.64886%
@depth 20 hitrate 3.42975%
@depth 21 hitrate 3.26378%
@depth 22 hitrate 3.03537%
@depth 23 hitrate 3.01364%
@depth 24 hitrate 2.80875%
What numbers should I expect?
Is using the startpos to test a problem?
Is my method of measuring wrong?
Is my replacment strategy wrong?
Am I gonna find true love?
These are the questions of life...
I thank in advance everyone that took the time to read this mess, and to answer to it, maybe!
Myrddin by default uses 512 MB, and a hash entry is 16 bytes. So, not very efficient, but functional.
.
