I have been playing around with a few new versions of Mediocre.
One version (which I call Mediocre v0.32full) includes all the tweaks I have tried so far, with things like; adaptive null move pruning, evaluation based LMR (it actually reduces more moves now), fractional plies, mate and move history in the board object, new extensions, restructured futility pruning, and some changes to evaluation.
I have had very mixed results with this version and until yesterday it played much weaker than v0.311.
Yesterday I tried only allowing null moves if the depth left was atleast 2 plies (which is the common way of doing it) and suddenly it started playing on par with v0.311. The results from the btm test suite is about as good as v0.311 but v0.32full searches about 1.5 deeper on average, which should be explained mainly by the greater number of moves reduced (apparently they are not all sound as of now).
I think there is a great deal of potential and there are probably a few more 'bugs' like this to work out.
Follow the process of creating a chess engine
Apr 24, 2007
Apr 20, 2007
[Other] Fixed
I have now updated and uploaded the correct files. Dangerous to do changes too early in the morning I suppose. :)
[Other] Whoops
I accidently updated the wrong sources so version 0.311 does not use null moves. I will upload the correct version in a few minutes. Sorry. :)
Apr 19, 2007
[New Version] v0.311 - Bug fix for winboard protocol
Changes:
mediocre_v0.311
- Fixed a bug that made the engine enter an infinite loop if it was mated using the winboard protocol
- Reworked the ended game draw detection using the winboard protocol (does not affect the search)
mediocre_v0.311
[Bug] Fixed the winboard protocol problem
When using the winboard protocol along with the Winboard interface and Mediocre got mated the engine entered an infinite loop. This happened because Winboard sends the mating move to the engine while for example Arena does not, it simply states the result once the game is over.
So what happened was the mating move was played on the board and then Mediocre started searching, but since it had no legal moves at the root node (since it was mated) the searchRoot returned -INFINITY as evaluation which got caught by the window check and a research was made, and since the evaluation returned never changed from -INFINITY the loop never exited.
Some poor programming from my side of course. I changed it so the root moves are generated before the iterative deepening loop (since they never change in the current search) and if no legal moves are found an empty pv is returned and handled by the input loop.
Thanks to H.G. Muller for sending me some games that made it easy to locate the bug.
So what happened was the mating move was played on the board and then Mediocre started searching, but since it had no legal moves at the root node (since it was mated) the searchRoot returned -INFINITY as evaluation which got caught by the window check and a research was made, and since the evaluation returned never changed from -INFINITY the loop never exited.
Some poor programming from my side of course. I changed it so the root moves are generated before the iterative deepening loop (since they never change in the current search) and if no legal moves are found an empty pv is returned and handled by the input loop.
Thanks to H.G. Muller for sending me some games that made it easy to locate the bug.
[Bug] Something with the winboard protocol
A few people have reported problems while using Mediocre with the winboard protocol.
I am quite certain the problem is with the 'end of game'-verification, I just have to locate it.
The reason I did not notice this earlier is I pretty much only use UCI when I run tournaments.
I will release a hotfix when I find the problem.
I am quite certain the problem is with the 'end of game'-verification, I just have to locate it.
The reason I did not notice this earlier is I pretty much only use UCI when I run tournaments.
I will release a hotfix when I find the problem.
Apr 15, 2007
[Guide] Fractional plies
Fractional plies are used to make it easier to tune extensions (and reductions).
If you have an extension that might not be worth extending a full ply, you could extend it 0.5 plies instead and only if you get two of those in the same branch the branch is extended with one ply.
The easiest way to make this work is change the way the search handles the depth altogether.
In Mediocre the call to alphaBeta from the root will look like this:
If we wanted to extend one ply we add 16 to the call, so the call would be depth-PLY+16.
To extend 0.5 plies the call would be depth-PLY+8 and so on.
When we run out of 'depth' the quiescent search is called and this happens pretty much automatically like this:
Fractional plies is very easy to implement (basically replace all depth-1 with depth-PLY) and is very handy to have.
If you have an extension that might not be worth extending a full ply, you could extend it 0.5 plies instead and only if you get two of those in the same branch the branch is extended with one ply.
The easiest way to make this work is change the way the search handles the depth altogether.
In Mediocre the call to alphaBeta from the root will look like this:
eval=-alphaBeta(board,current_depth*PLY-PLY,-beta,-alpha,true,1);Where PLY is a fixed number that represents a full ply, 16 for instance. So if we wanted to search to 10 plies we would call alphaBeta with 10*16-16 = 144, which means we call it with 9 plies left to go.
If we wanted to extend one ply we add 16 to the call, so the call would be depth-PLY+16.
To extend 0.5 plies the call would be depth-PLY+8 and so on.
When we run out of 'depth' the quiescent search is called and this happens pretty much automatically like this:
if(depth < PLY) do_quiescent();Meaning we do not have a full ply left to search so we start the quiescent search (which does not keep track of depth so we do not have to worry about it there).
Fractional plies is very easy to implement (basically replace all depth-1 with depth-PLY) and is very handy to have.
[Other] Test sets
Up until now I have been testing additions to Mediocre by trying it on random positions and basically look at the node count and time to decide if the addition was an improvement or not.
Once I started to feel satisfied with a new version I ran as many games as I had patience for, somewhere between 100 and 1000, against the last version and a couple of other engines.
I never really ran into any problems using this crude way of testing since pretty much every addition and change resulted in a very noticeable improvement.
However recently I have been having some serious trouble determining if new changes actually improves the engine or not, so it is time to refine my methods a bit.
New way of testing
Quick test: Run the YATS test sets selected.pgn and tony.pgn at 5 seconds per position, and analyze the results with Pro Deo 1.4. This takes 3.5 minutes and gives a general idea of the effect of the change(s).
Mediocre v0.31 got the following results:
Mediocre v0.31 got this result:
By using a fixed set of openings a lot of the randomness is taken out and it should be easy to determine if the new engine is an improvement and by how much.
100 3-minute games take somewhere between 5-10 hours, probably closer to 5.
Why YATS
YATS is a testing system created by Ed Schröder, that instead of giving 0 points for a wrong answer and 1 point for a right answer rewards 0-10 points depending on what move the engine chooses. 10 for the 'correct' move and less for alternative moves that might still be good.
For a mediocre engine, like Mediocre, this is a perfect way of analyzing its strength. It might not find the 'best' move very often, but usually find a decent alternative move in the same position.
This way even one analyzed position might supply some interesting information, an old version might find an alternative move that gives 2 points while the newer version finds a slightly better alternative that gives 5 points. The traditional test sets would reward 0 points for both versions.
Further reading on the YATS-site.
And stick to it
Having set up this testing structure I do not intend to change it for quite some time, except for perhaps adding a fixed depth search to the YATS sets as well.
By having it unchanged like this it will be much easier to determine individual strength of the different versions over time without having to run thousands of games just to avoid the inherent randomness of openings and in fact chess in general.
Once I started to feel satisfied with a new version I ran as many games as I had patience for, somewhere between 100 and 1000, against the last version and a couple of other engines.
I never really ran into any problems using this crude way of testing since pretty much every addition and change resulted in a very noticeable improvement.
However recently I have been having some serious trouble determining if new changes actually improves the engine or not, so it is time to refine my methods a bit.
New way of testing
Quick test: Run the YATS test sets selected.pgn and tony.pgn at 5 seconds per position, and analyze the results with Pro Deo 1.4. This takes 3.5 minutes and gives a general idea of the effect of the change(s).
Mediocre v0.31 got the following results:
Testset : selected.pgnFull test: Run the btm.pgn (Beat the Masters) YATS set at 1 minute per position. This takes 2 hours 46 minutes and should give a very good idea of the strength of the engine.
Level : 5 seconds
Engine : Mediocre 0.31
Positions : 26
Found : 1 (3.8%)
Maximum points : 260
Scored points : 145 (55.8%)
Maximum time : 2:10
Used time : 2:05
Testset : tony.pgn
Level : 5 seconds
Engine : Mediocre 0.31
Positions : 16
Found : 2 (12.5%)
Maximum points : 160
Scored points : 69 (43.1%)
Maximum time : 1:20
Used time : 1:17
Mediocre v0.31 got this result:
Testset : btm.pgnIf this results in an expected improvement to the engine run a 100 3-minute game match between the previous version and the new version using the sherwin50.pgn test set (by Michael Sherwin). 100 games means two games per opening so each version gets to play both sides.
Level : 60 seconds
Engine : Mediocre 0.31
Positions : 166
Found : 32 (19.3%)
Maximum points : 1660
Scored points : 993 (59.8%)
Maximum time : 2:46:00
Used time : 2:20:43
By using a fixed set of openings a lot of the randomness is taken out and it should be easy to determine if the new engine is an improvement and by how much.
100 3-minute games take somewhere between 5-10 hours, probably closer to 5.
Why YATS
YATS is a testing system created by Ed Schröder, that instead of giving 0 points for a wrong answer and 1 point for a right answer rewards 0-10 points depending on what move the engine chooses. 10 for the 'correct' move and less for alternative moves that might still be good.
For a mediocre engine, like Mediocre, this is a perfect way of analyzing its strength. It might not find the 'best' move very often, but usually find a decent alternative move in the same position.
This way even one analyzed position might supply some interesting information, an old version might find an alternative move that gives 2 points while the newer version finds a slightly better alternative that gives 5 points. The traditional test sets would reward 0 points for both versions.
Further reading on the YATS-site.
And stick to it
Having set up this testing structure I do not intend to change it for quite some time, except for perhaps adding a fixed depth search to the YATS sets as well.
By having it unchanged like this it will be much easier to determine individual strength of the different versions over time without having to run thousands of games just to avoid the inherent randomness of openings and in fact chess in general.
Apr 14, 2007
[Other] Stack done
I now have a working stack done for the Board class. It keeps track of trivial things like castling rights and en passant squares to make unmakeMove possible, but also what moves were played to reach the position and if the position is a check or not.
Things like determining if the last move played (i.e. in the last instance of the recursive alpha-beta) was a promotion, or a capture, or a check etc. are very simple now.
I should have done this a long time ago, but well, the first thing I wrote was the Board class and I simply did not realize what was really needed in it back then.
As I said the makeMove method now determines if the position before making the move is a check or not. I do not know if this is really nescessary, but considering pretty much every node uses this information in one way or another it is probably ok.
The problem is deciding if the next move to be played will be a check without actually playing it on the board. This is another matter though and I will probably implement a gen_checks to take care of that.
Anyway the way it works now the move generation is about 20% slower than without the checks, but all in all it should turn out to be slightly faster when used in the search. And most importantly it will make things like futility pruning and LMR much easier to adjust.
Things like determining if the last move played (i.e. in the last instance of the recursive alpha-beta) was a promotion, or a capture, or a check etc. are very simple now.
I should have done this a long time ago, but well, the first thing I wrote was the Board class and I simply did not realize what was really needed in it back then.
As I said the makeMove method now determines if the position before making the move is a check or not. I do not know if this is really nescessary, but considering pretty much every node uses this information in one way or another it is probably ok.
The problem is deciding if the next move to be played will be a check without actually playing it on the board. This is another matter though and I will probably implement a gen_checks to take care of that.
Anyway the way it works now the move generation is about 20% slower than without the checks, but all in all it should turn out to be slightly faster when used in the search. And most importantly it will make things like futility pruning and LMR much easier to adjust.
[Other] The joys of bug hunting
After some reconstructing of the makeMove, umakeMove, makeNull and unmakeNull methods I ran into a long streak of errors popping up in just about all positions.
I sat for a few hours commenting out all complicating code like transposition tables, null moves, futility pruning, quiescent search etc. trying to isolate the error but it kept appearing at the exact same spots. The perft numbers worked perfectly, so I had to look for the error in the search.
So I started printing the moves to see if I could find a pattern. I had found a position where the error appeared after 'only' 3000 nodes so the print out was atleast manageable.
At first I thought it was the legal move check that was the problem because that was the most obvious thing that was made differently from a plain perft search.
However, after 4 hours or so I concluded it had something to do with captures and it seemed to involve the hash move.
By then the time was 2am so I decided to try in the morning. And with a fresh mind I immedatiatly drew the obvious conclusion... hash moves depend on zobrist keys to work correctly of course, and there is a code segment in the makeMove method that updates the zobrist for captures.
And of course there the problem was, I had 'simplified' that part of the code and instead of removing black pieces from the zobrist I removed white and vice versa.
So it was the 'other' thing the search does differently execept for legal moves, it uses a transposition table. :)
This was so much fun I almost considered starting to put in intentional bugs just to enjoy solving them. Or not.
I sat for a few hours commenting out all complicating code like transposition tables, null moves, futility pruning, quiescent search etc. trying to isolate the error but it kept appearing at the exact same spots. The perft numbers worked perfectly, so I had to look for the error in the search.
So I started printing the moves to see if I could find a pattern. I had found a position where the error appeared after 'only' 3000 nodes so the print out was atleast manageable.
At first I thought it was the legal move check that was the problem because that was the most obvious thing that was made differently from a plain perft search.
However, after 4 hours or so I concluded it had something to do with captures and it seemed to involve the hash move.
By then the time was 2am so I decided to try in the morning. And with a fresh mind I immedatiatly drew the obvious conclusion... hash moves depend on zobrist keys to work correctly of course, and there is a code segment in the makeMove method that updates the zobrist for captures.
And of course there the problem was, I had 'simplified' that part of the code and instead of removing black pieces from the zobrist I removed white and vice versa.
So it was the 'other' thing the search does differently execept for legal moves, it uses a transposition table. :)
This was so much fun I almost considered starting to put in intentional bugs just to enjoy solving them. Or not.
Subscribe to:
Posts (Atom)