Mar 16, 2007

[Other] Evaluating new features

I ran a couple tournaments to test the new features LMR, SEE and an attempt at a more dynamic time management.

Trying LMR

The first tournament is a 200 game match between Mediocre v0.241b and a version with LMR that decides what to reduce based on the move being a capture or not, the current depth, and if the position before the move had one of the kings in check. It does this after searching four moves to regular depth (usually hash move, killer moves and one more).

Obviously this is a quite loose way of handling the reductions, so plenty of moves are going to get reduced. This made me unsure how sound the LMR was going to be, so the result came as a bit of a surprise:
   Engine           Score
1: Mediocre LMR 132,0/200
2: Mediocre v0.241b 68,0/200
The LMR really pays off it seems, and that is with hardly any limits as to what gets reduced after the first four moves.

This was the base of the assumption I made in my last post about the upcoming Mediocre v0.25b having a rating of about 2050 (about 100 points higher than v0.241b).

The 'previous position in check' seems quite useless as a condition when deciding what to reduce, I simply put it in there because we have the information free from the check extension heuristic. Better obviously, is checking if the move up for reduction is a checking move, and if it is, not reduce it. If we do not have that condition the check extension is effectively cancelled out.

So in the next test tournament I changed that and also added a couple of different setups with SEE.

Trying LMR and different setups of SEE

There are numerous ways to use the static exchange evaluation in the search (as well as in the positional evaluation, but I have not gotten to that yet).

It can be used for better sorting of both the quiescent search moves and ordinary search moves. Also in the quiescent search we can prune out losing captures since they should not come up with anything interesting (good sacrifices are handled by the ordinary search) as mentioned by Ed Schröder.

So we have a few possible combinations. In this tournament I decided LMR with 'current' in-check condition is better than 'previous' in-check (based on a few mini tests they surprisingly enough seems quite equal), so I went with that for all the SEE-versions. Every other condition for LMR is the same (4 moves to full depth, do not reduce 3 plies from the horizon, and do not reduce captures).
clmr -> LMR does not reduce checking moves
plmr -> LMR does not reduce previous positions in check
ss -> SEE sorting in ordinary search
qs -> SEE sorting for quiescent moves
qsp -> Same as qs but prunes losing captures
nt -> New time mangement (didn't work out too great)
If not mentioned, it is the same as in v0.241b (quiescent search being ordered with the ordinary MVV/LVA setup for example).

The tournament had a total of 375 games (25 games between all engines) and these were the results:
   Engine                     Score 
1: v0.25b (clmr,ss,qsp) 79,5/125
2: v0.25b (clmr,ss) 71,0/125
3: v0.25b (clmr,ss,qs) 66,5/125
4: v0.25b (clmr,ss,qsp,nt) 66,5/125
5: v0.25b (plmr) 57,0/125
6: v0.241b 34,5/125
The version with quiescent pruning seems to be the best, but worse with my new clumsy time management.

As usual we have too few games to make any real conclusions, but I will go for quiescent search pruning, it seems to make a difference for the better, and SEE ordering in ordinary search is clearly beneficial.

Splitting up the table for statistics of version vs. version is rather useless with such few games, but here is a table for the v0.241b against the others:
-----------------Mediocre v0.241b------------------
v0.241b-v0.25b (clmr,ss) : 6,5/25 4-16-5 26%
v0.241b-v0.25b (clmr,ss,qs) : 8,5/25 7-15-3 34%
v0.241b-v0.25b (clmr,ss,qsp) : 6,0/25 4-17-4 24%
v0.241b-v0.25b (clmr,ss,qsp,nt) : 5,5/25 4-18-3 22%
v0.241b-v0.25b (plmr) : 8,0/25 5-14-6 32%
In conclusion v0.241b got horribly beaten by all the new versions. :)

Elostat

The last analysis of this tournament is done by Elostat, a utility by Frank Schubert for determining rating differences between the engines from PGN files. I set the starting rating to 2090 to get v0.241b to about a rating of 1953 as suggested by Le fou numérique.

These were the results:
  Program                   Elo   +   -   Score
1 v0.25b (clmr,ss,qsp) : 2172 56 55 63.6%
2 v0.25b (clmr,ss) : 2131 55 55 56.8%
3 v0.25b (clmr,ss,qsp,nt) : 2110 55 54 53.2%
4 v0.25b (clmr,ss,qs) : 2110 54 54 53.2%
5 v0.25b (plmr) : 2066 54 54 45.6%
6 v0.241b : 1952 60 62 27.6%
I cut out a few statistics to make the table fit, the layout of this page is not very forgiving. :) The '+' and '-' is the error margin for the elo-ratings. Using the error margins it seems Mediocre is about to gain somewhere between 105 and 338 elo points.

Not too bad I guess. :)

Mar 14, 2007

[Other] Rating estimations

The french site Le fou numérique is regurarly estimating the rating of new versions of UCI chess engines.

I hunted down all the estimations Mediocre has gotten and tried to fill in some of the blanks. v0.22b never got an estimate on the site, and v0.12b got a very high estimate (1578) for some reason (this does not reflect the tourneys I have done with it).

Below is a list of the ratings for the different versions of Mediocre. The 'estimated' ratings is results from my own tourneys and the rest is from Le fou numérique.

The numbers should be taken with a grain of salt, for example the difference between v0.232 and v0.231 is almost 100 points, while there is no real difference between those versions (v0.232 got automatic protocol detection, perhaps that helped it play better with Le fou numérique's software, who knows).

However this is also true for the other engines, so take it for what it is, a crude estimate.
Mediocre 0.25b     : 2050 (estimated)
Mediocre 0.241b : 1942
Mediocre 0.232b : 1832
Mediocre 0.231b : 1753
Mediocre 0.22b : 1650 (estimated)
Mediocre 0.2b : 1378
Mediocre 0.12b : 1278 (estimated)
For some comparison here are a few other engines.
GreKo 5.1          : 2265
Winner of WBEC 14, division 5
Gibbon 2.31d : 2157
Qualified for promotion phase of WBEC 14, division 5
Clueless 1.3.4 : 2004
Qualified for second phase of WBEC 14, division 5
BiBiChess 0.5 : 1991
Top half of first phase of WBEC 14, division 5
Roce 0.0350 : 1758
Bottom half of first phase of WBEC 14, division 5
Obviously these numbers mean quite little. They are a very rough estimate of the individual strength of the different engines. In matchups they probably do not hold up too well.

But it is fun to play around with numbers like this without actually having played thousands and thousands of games for statistically accurate rankings.

[Plan] Static exchange evaluation, late move reduction and new time management

I am currently working on some rather powerful additions to Mediocre.

SEE

The static exchange evaluation is probably the most needed one. It is a way of determining if a capture is winning or losing material without actually playing out the sequence on the board. We simply count the number of pieces attacking the square for both sides, and order them so we always capture with the least valuable piece first.

This way we get a good idea if a capture is winning or losing with little time used.

This information can then be used for better sorting of quiescent search moves and also for the main sorting of moves. For the main sorting, winning captures is more likely to produce good results than even the killer moves, and equal captures should be sorted before losing captures obviously.

The problem is writing a good algorithm for this since it will be called very often. If it is too slow the gains will diminish fast. I have taken a good look at the Scorpio and Glaurung engines way of doing this and I think I got it to work very well.

The code is quite complex and I will write a thorough guide when the next version of Mediocre is ready.

LMR

As opposed to null moves that reduce moves which are likely to fail high (be too good), late move reductions reduce moves that are likely to fail low (not reach up to alpha).

The way it works is we start by searching the first 3-4 moves to full depth. In Mediocre these should be the hash move, the killer moves, and possible a move from the history heuristic or a capture sorted high with MVV/LVA (once SEE is implemented winning captures will be among these as well).

Then we reduce the depth of the rest of the moves with 1 and search with a minimal window. If the move by chance surprises us and returns a value bigger than the previous best move, we research the move with full depth.

It is very rare that one of the remaining moves produce better results so this technique saves quite some time. However we need to be careful to not reduce mindlessly. We do not want to reduce moves that we think leads to something interesting. For example we can not reduce checks, since that will cancel out the check extension. Also captures are risky to reduce.

There are several more ways to determine if we should allow reducing a move. For example if a move has failed high often in the passed it is not a good candidate for reducing, we can also check the static evaluation and see if reducing is a good idea (if static evaluation is currently below alpha we should probably not reduce any moves).

There are a few more considerations that can be done as well and I am currently experimenting with what works best for Mediocre. I will get back with a more thorough analysis.

Time management

Currently Mediocre uses a fixed percent of the time on every move (2.5% + increment/2). This is a very crude way of handling the time assignment.

I have been looking at a number of considerations to make the time management more dynamic. Things like different time usage for different kinds of positions, using more time if the evaluation drops drastically after an iteration and spending a bit extra time when getting out of the opening book.

Also using the best move from aborted searches (where we ran out of time and exited the search) is an option as pointed out to me by Greg Schmidt.

All in all there are a lot of things to consider when deciding how much time to use for a move, and the best part is we can have very advanced ways of determining this since it is only done once per search and will not have a big impact of the total time usage.

Mar 9, 2007

[Other] A little test tourney

I ran a small tourney (300 games) to test the internal iterative deepening added in the latest version. The results were:
   Engine  Score         1         2         3
1: v0.241b 122,0/200 * 52.0-48.0 70.0-30.0
2: v0.24b 114,5/200 48.0-52.0 * 66.5-33.5
3: v0.232b 63,5/200 30.0-70.0 33.5-66.5 *
As you can see the 0.24 version with its adjusted evaluation is plenty stronger than the 0.23 version. However there is not much difference between the version with iid and the one without (the result between them 52-48).

I will keep working on this and see if we can get it to do better.

Mar 7, 2007

[New Version] v0.241b - Internal iterative deepening and changed back eval output

Changes:
  • Internal iterative deepening was added along with hash move search before generating moves
  • The aspiration windows were reduced to 10 centipawns
  • The evaluation output was changed back to show the eval from the engine's point of view
Note: The internal iterative deepening does a mini-search (half the remaining depth) if there is no hash move for the current position. This mini-search finds a plausible move that will be tried first.

Once we have a hash move it will be searched before generating any other moves, that way if we get a cutoff from it (which should be quite likely) we saved some time.

I have chosen to not check the hash move for validity as of now. This can be risky since it is possible for two different positions to have the same zobrist key (possible but highly unlikely). I will probably add some sort of verifier in upcoming versions.

mediocre_v0.241b

[Bug] Evaluation was right

In the last version I simply negated the evaluation output if Mediocre was playing black. This way a 'positive' score would be reported as negative, meaning black was ahead, instead of positive (engine is ahead).

While this seem more logical to me, unfortunately the protocols does not work this way. The evaluation should always be in terms of the engine, and not on what side is ahead.

Fortunately the thinking output does not affect the actual thinking of the engine, BUT some interfaces (like Arena) adjudicate games based on the evaluation of the engines. This can lead to Arena adjudicating a game since it thinks Mediocre considers its position very bad, while in fact it considers it very good.

I will change it back in the next version.

Mar 6, 2007

[New Version] v0.24b - Adjusted evaluation and bug fixes

Changes:
  • The evaluation was readjusted, resulting in quite an improvement in overall strength
  • Fixed an issue with the force mode in winboard, was not leaving force mode on the 'new' command
  • Added searchRoot() that works a bit differently on root nodes than ordinary alpha-beta, this should take care of the rare occasions where Mediocre did not have a move to make
  • The thinking output now shows white ahead as positive value and black ahead as negative value, the evaluation output no longer depends on what side the engine is playing
  • Fixed the contempt factor again, hopefully it works now (slightly negative number for the draw if white is moving, and slightly positive if black)
Note: The changes in evaluation were all quite minor. Added bonus for bishop pair and readjusted a few of the piece tables to encourage development, also slightly increased bonus for rooks on open and semiopen files, and slightly decreased the bonus for king attacks with two and three pieces (the old evaluation would go bananas over even a slight chance of attack).

But all together it really increased the overall strength of Mediocre.

mediocre_v0.24b

[Bug] No move reported and winboard force mode (again)

The first bug has haunted me since transposition tables were implemented. Occassionally (every 20th game or so) Mediocre seemed to stop running and not report any move to be played. The engine did not crash and it did not misinterpret the interface output in any way.

After some research the only explanation I can give is this is due to the position where the search started was overwritten with some deeper searched position in the transposition table. Hence the position can not be found when we traverse the transposition table for the principal varation. And since the 'bestmove' sent to the interface is dependant on the first move in the principal variation, no move is sent.

I hoped the depth/new replacement scheme would take care of this, but in retrospect this hope was futile since the second entry (the 'new' entry) is replaced very often.

In the upcoming version of Mediocre I have added a searchRoot-method that only handles root nodes (that is the first set of moves the engine has to choose from and of which one will ultimately be played). This method is called from the iterative deepening loop, and from here it calls alphaBeta for every root move.

This way we will always know what move was chosen as the best, and we can base the principal variation output on this. Now the worst thing that can happen to the pv-output is we only get the best move and nothing more (instead of best move plus the rest of the expected line), this should happen very rarely (every 20th game or so as mentioned) so it is no big deal.

There are also other benefits to be gained from this approach, since the root is only iterated 30-35 times on average (the number of available moves) we have room for things like more advanced move ordering, reporting the currently searched move etc. Anything we do here will have little effect of the overall performance of the search.

Also we should not probe the transposition table at the root node to check for cutoffs. I have done this before, but all we are interested at the root node is what move to be played.

So all in all this change was needed, and hopefully the annoying bug is gone for good.

Winbord force mode

The winboard protocol clearly states that when the 'new' command is sent, the engine should exit force mode. I simply overlooked this and therefore Mediocre has not been able to play to games in a row if it is black in the second game. This was only noticeable under certain circumstances though since some interfaces handles this more loosely, and also restarts the engine after a game.

However, when a new game is about to start the winboard interface sends:
force
followed by
new
I am not entirely sure what the point of the force command there is, but probably it has something to do with preparing the engine for any possible starting moves that might come.

Anyway after this the interface sends 'go' if the engine is white, since it should move, but only 'usermove [move]' if the engine is black.

So it is imperative we exit the force mode on the 'new' command, or else the engine will only play the 'usermove' on the internal board, but not start thinking about an answer.

Mar 4, 2007

[Other] Slowing down a bit

The last three months I have been spending hours every day on Mediocre. For the next month or two I will be slowing down a bit and work on bug fixes and tweak the evaluation a tad. I do not plan to implement any big changes during this time.

I think this is important so I do not end up with a big unmanageable engine that I do not have any overview of.

I also have a few exams coming up that I need to spend time on, so this is a good time to do it after getting all the major parts of Mediocre done.

There are still plenty of things I want to implement and change, but that time will come.

I will report from any 'official' tournament Mediocre participates in. Recently for example it played in a test tournament on Le Fou numérique with quite a pleasing result.
1 Mediocre 0.232b  10,5/14  ·· 0= 01 11 01 11 11 11
2 Philemon C 10,0/14 1= ·· 1= =0 01 11 1= 11
3 Heracles 0.3.0 9,0/14 10 0= ·· 10 11 01 =1 11
4 Piranha 0.5 9,0/14 00 =1 01 ·· =0 11 11 11
5 ApilChess 1.05r1b 7,5/14 10 10 00 =1 ·· 10 01 11
6 T.rex 1.8.5 5,0/14 00 00 10 00 01 ·· 11 10
7 NSVChess 0.14 4,0/14 00 0= =0 00 10 00 ·· 11
8 Ace 0.1 1,0/14 00 00 00 00 00 01 00 ··
If there is anything you want me to clarify or write about post a comment or send me a note, I will also probably write a guide or two about the latest changes. So keep checking in. :)

Mar 2, 2007

[New Version] v0.232b - Automatic protocol detection

Changes:
  • Mediocre now automatically detects what interface is being used, no parameter is needed
Note: This is another tiny fix in my continued quest to make Mediocre work in all interfaces. The jlaunch solution was hardly brilliant so I decided to drop it and let people use Jim Ablett's executables instead.

But then a new problem arrives, Shredder and Chessbase does not accept parameters on engine startup (like Arena) so Mediocre does not start correctly (or actually it starts to the line input mode which does not recognize anything).

With this new version Mediocre starts and waits for the first command from the interface, if it is "xboard" it switches to xboard, if it is "uci" it switches to uci, and for anything else it goes to line input. This means you will have to type in a 'dummy' command to enter the line input mode, but that is a minor nuiscance.

mediocre_v0.232b