Jan 31, 2007

[Guide] Contempt factor

This is a rather minor tweak to the draw evaluation of a position. It is used to avoid easy draws.

It simply subtracts a certain constant from the draw evaluation, so instead of returning 0 if a position is repeated it could return -50, this way the engine avoids taking the draw unless it is down with more than 50 points.

In Mediocre I added a check at the beginning of the search deciding what phase of the game we are in (opening, middle game or ending). Like this:
int gamePhase = Evaluation.getGamePhase(board);

if(gamePhase == PHASE_OPENING)
contemptFactor = CONTEMPT_OPENING;
else if(gamePhase == PHASE_ENDING)
contemptFactor = CONTEMPT_ENDING;
else
contemptFactor = CONTEMPT_MIDDLE;
The game phase is decided by how many pieces both sides have left.

For now I have set the different contempt values to 50 for opening, 25 for middle game and 0 for ending. And when a draw is found I simply add the contempt factor to the draw value like this:
return -(DRAW_VALUE + contemptFactor);
This way the draw value will be worse depending on what phase we are in.

This does not affect the playing strength of the program (if done right), but avoids some useless draws.

[Other] A couple results

There is still an annoying bug lurking somewhere in the code. I am quite sure it has to do with the time management, sometimes the engine simply does not start searching. It does not crash, and it does not fail receiving a principal variation, it is just skips searching. Hopefully I can track it down soon.

Anyway here is a couple interesting tournament results.

The first was played between Mediocre v0.2b and Mediocre v0.12b.
   Engine          Score    Me v0.2b  Me v0.12b 
1: Mediocre v0.2b 9,0/10 ·········· 11==111111
2: Mediocre v0.12b 1,0/10 00==000000 ··········
As you can see the new version completely annihilated the old. The two draws were due to middle game repetitions, where v0.12b was up a fraction of a pawn and v0.2b took the draw. This will be solved with a contempt factor which I will add soon. It avoids taking draws if he engine is not behind a certain amount.

Since both engines used the same evaluation scheme the wins are explained solely by the deeper search possible with transposition tables (along with some of the other changes like faster move ordering).

Happy days! :)

After finishing with the transposition tables I went on to improve the evaluation slightly. I added some development evaluation like rewarding the king moving to the side with pawns protecting it (I will not add a bonus for castling since I prefer letting the engine decide if castling is the best option for protecting the king) and not leaving pieces on the first rank.

Also moving the king out in the ending is rewarded. The result from these simple changes was this:
      Engine       Score      Me dev   Me v0.2b
1: Mediocre dev 9,5/10 ·········· 11111111=1
2: Mediocre v0.2b 0,5/10 00000000=0 ··········
The draw was a forced perpetual check found by v0.2b while being down a piece in the ending.

Mediocre is quickly improving. Perhaps it is time for me to take it on and see if I stand a chance. In blitz games it beats me more often than not, but I am not so sure about how it stands in longer time controls.

Jan 30, 2007

[New Version] v0.2b - Transposition tables

Changes:
  • Transposition tables are implemented along with a new draw detection scheme
  • There is now a zobrist key field in the Board-class, the key is updated when making and unmaking moves, but can also be generated from scratch with the static getZobristKey-method in the Zobrist-class
  • Changed pv search so it is only used if a best move has been found
  • Sorting moves is now done with a much faster bubble-sort method
  • Changed move generation slightly and added a new filterQuis-method which adds the right values to the captures
  • Quiescent search now re-uses the moves generated in the alphaBeta method
  • Mediocre is now developed in Eclipse so the folders look a bit different
  • The .bat-files now point to "/bin/" so they work as long as they are kept in the original folder (you should not have to update the path in them anymore)
  • Sorting methods are completely rewritten, based on orderingValue
  • Preliminary orderingValues are added to moves at generation time
  • Move-objects now have a orderingValue used in sorting
  • Implemented fixed depth search, call Engine.search() with depth>0 to use, call with depth=0 for time control mode
  • The line input can now be used to play games with fixed depth (5 for now) if you enter moves on the form "e2e4" etc. It is still very crude and is supposed to be used for testing
  • Plus many minor tweaks and changes

Note: Although I have tested this version extensively I am quite sure there is still a bug or two hiding, feel free to report any odd behaviour you might find. Also I wanted to get this out as fast as possible so some of the new code lack comments, and there might be some trace code still left in. Nothing that effects the play though.

Thanks to Casper W. Berg, Mark Lefler and Gary on TalkChess.com who helped me with a few bugs.

mediocre_v0.2b

Edit:
I forgot to change the version numbers in the release. This is now fixed.

[Guide] Transposition tables

After exactly three weeks since the last release it is finally time for the transposition table guide and after this the new version of Mediocre.

Beware, the transposition tables introduces a whole range of new possible bugs, as well as reinventing old ones. I for one should know after these three nightmare weeks. :)

In this guide I will go through the basic idea of a transposition table, as well as hashtables and things like replacement schemes and avoiding collisions.

What I will not cover is the memory usage issue. This is very implementation specific and quite complicated. I will be using a hashtable (an array) with 1048583 positions (2^20 + 7 to make it a prime number), it seems to work ok, but frankly I do not know how much memory it would use if filled completely with the moves being stored as objects etc.

I will most likely get back to the memory issue in the future when it is time for optimizations, but for know I will assume the hashtable is of a suitable, fixed, size.

Transposition Table basics

We start with the basics. A transposition is a position that can occur after different sequences of moves. For example:

This position can occur after:
1. d4 d5
2. c4 ...
As well as:
1. c4 d5
2. d4 ...
It makes no sense calculating this position again since we should already know what the best move is from here.

Let us say we searched 8 ply from the start position and found a line:
1. d4  d5
2. c4 c6
3. d3 e6
4. Nf3 Nc6
and evaluated it to +10.

When we get to this position after 1. c4 d5 2. d4 ... we already know that the best answer black has is c6 and the evaluation is +10.

So we just saved 5 plies of searching.

In general, opening and middle game positions do not offer that many useful transpositions and the gains are fairly limited, but in the endings, especially king and pawn endings, the number of transposition are very common and the gains from using a transposition table enormous.

But this is not all, and not even the most important factor. As mentioned before alpha-beta search relies heavily on move order. If the best move is searched first the alpha-beta can cut off many more lines, thus being much more effective.

Moves from earlier searches, that is moves in the transposition table, tend to be very good moves, even though they might not have been searched to deep enough depth in the earlier search to completely replace the search. If we search this move first every time, we have a good chance of hitting the best move much more often.

This helps more than any other move ordering improvement schemes (like killer moves or history heuristic).

Hashtables

Earlier I have been talking about transposition tables and hashtables like they are the same thing. That is not quite true though. A transposition table uses a hashtable to store the searched positions.

A hashtable can be used for many things, one common use is hashing files on the internet, that is giving them a unique key, and storing the keys in a table so we do not need the file-name (or the whole file) to find the file. The hashing is the same as our Zobrist keys (we give every position a unique key).

Storing large ranges in a smaller table

A hashtable is a way to store a large range of values into a smaller, more manageable table.

If we move 10 plies from the start position we have about 70 trillion possible positions.

As explained earlier we use Zobrist keys to represent the positions. They look like this:
2809723212531837306
6543248948113846523
8949841559963541289
As stated before they do not cover all positions, but they would by far cover the 70 trillion originated from the starting position.

So if we want to store the searched positions we might think we need a table with atleast 70 trillion positions available. And then use the index to find the position we were looking for. Like this:
Index                   Zobrist key and eval etc.
.
.
.
2809723212531837306 2809723212531837306 (+ eval etc.)
2809723212531837307 2809723212531837307
2809723212531837308 2809723212531837308
.
.
.
6543248948113846523 6543248948113846523
6543248948113846524 6543248948113846524
6543248948113846525 6543248948113846525
.
.
.
Of course if we wanted to store all positions we would have to do like this. But a table with 70 trillion places takes up a lot of space, so it is hardly possible anyway.

Now luckily enough alpha-beta (and other pruning methods) cuts off most of the positions. So we would get something like this:
Index                   Zobrist key and eval etc.
.
.
.
2809723212531837306 empty
2809723212531837307 empty
2809723212531837308 empty
.
.
.
6543248948113846523 empty
6543248948113846524 6543248948113846524
6543248948113846525 empty
.
.
.
Now we get a whole bunch of empty space instead, but the table is still huge.

Let us say we had a super effective alpha-beta algorithm and only got 100 evaluated positions after the 10 ply search.

Instead of storing those 100 Zobrist keys in a huge table with trillions of unused spots we use a hashtable.

The hashtable has much less spots, the bigger the better of course, but let us use 1000 just as an example (this is an extremely small hashtable). So it could look like this.

Index Zobrist key and eval etc.
0 5423248948113846000
1 empty
2 empty
.
.
.
500 empty
501 empty
502 1863548654542656502
.
.
.
998 empty
999 4564813548868468999
empty

Hash function

Ok, good. So we have a much smaller table and still fit all the positions we searched in it. But in what index should we store a certain position and how do we know where it is?

Index 0 for example does not tell us anything of what position is stored there.

The solution is a hash function. We apply a certain function to the Zobrist key to receive a value between 0 and 999.

That hash function is usually (you can use whatever you want, but this is very easy and logical):
[zobrist key]%[total size of the hashtable]
The % is called 'modulus' and works like division but returns an integer, cutting off any decimals the division might get.

In Java this is written something like:
int hashkey = (int)(zobrist%HASHSIZE);
We want the hashkey to be of type 'int' so we can use it for index, but the zobrist key is of type 'long' for we need to reformat it to 'int'.

So let us say we have the Zobrist key 6543248948113846523. We then apply the hash function:
6543248948113846523 % 1000 = 523
So we store that position at index 523.

Now when we want to look up our position we simply apply the hash function to our zobrist key and we get the index we need to find.

As you might have noticed, taking any big number modulus 1000 returns the last three digits, this is not true for other numbers though. The size we use for the hashtable is, as I mentioned in the beginning, determined by how much memory we can spare. The bigger hashtable the more positions we can store in it.

Of course we have an obvious problem here, the keys:

1863548654542656502 and 3549874513549875502

would hash to the same index, 502, if we had a hashtable of size 1000. This is called a collision. More about that further down.

Transposition table entries

Now we have a way of storing searched positions, so we need to figure out what information we need about the position.

The less you store the bigger your hashtable can be with the same amount of memory. For example if you, like me, store a whole Move-object at every entry, your hashtable will not be able to hold nearly as much as if you stored a string like "e2e4" or even just an integer representing the move.

Once again I will not consider the memory factor here though.

The following is a list of the most important information, there are other things like mate-values, but these are the basics:
  • Zobrist key

    As I mentioned above two different positions can hash to the same index, so we need a way to make sure we actually have the right position before we use the values in it. The simplest way of doing this is storing the zobrist key, and every time we are about to use an entry, we first compare the zobrist keys, making sure we have the position we were looking for.

    There are other ways of doing this, like just storing half the zobrist key (to save space), but the full zobrist key is the easiest and safest way.

  • Depth

    To get this right we need to do a bit of thinking.

    A depth of '0' means we stored the position based on an evaluation on a leaf node (a horizon node). A depth of '1' means we stored the position on a frontier node and so on.

    So if we run into a transposition with the stored depth '5'. We know that the evaluation attached to it is based on 5 more plies of searching.

    This is very important since if we are about to search a position to a depth of 8 ply, and at ply 3 we run into a transposition that we found in a 4 ply search, we can not use the values we have for it. This is because those values are based on a 4 ply search which is much weaker than the expected 8 ply.

    The found position would have depth '1' attached to it, since we had 1 more ply to search when we stored it in the 4 ply search.

    But in the 8 ply search our depth would be '5' when we encountered it, since we had 5 more plies to search.

    So we are not going to use the values in the hash entry, except for searching the move attached to it first. Like I mentioned above this move is usually good.

    In programming terms we would do this check before using values from the transposition table:
    if(hashentry.depth >= ply)
    // Use the values attached

  • Evaluation

    This is the evaluation we received for the position. This is pretty straight forward as long as we know what kinds of values we store.

    In Mediocre the Evaluation method returns a positive score if the side on the move is ahead and a negative score if it is behind. This means +100 means black is ahead if it is black to move when the evaluation is made.

    So if we store the evaluation just like it was received in the alpha-beta we will alternate between positive and negative scores, even if the position is always 'positive' for say white.

    This is not a problem, and I did it like this in Mediocre. As long as we know what values we store. This was one of the first major bugs I had, the evaluation alternated from negative to positive for every step in the iterative deepening. The problem was I handled the evaluation like it was always positive if white was ahead, which it of course was not.

  • Flag

    Here is another important piece of information that might not be obvious at first.

    There are three different kinds of evaluations in the alpha-beta search:

    Exact evaluation (HASH_EXACT in Mediocre), when we receive a definite evaluation, that is we searched all possible moves and received a new best move (or received an evaluation from quiescent search that was between alpha and beta).

    Beta evaluation (HASH_BETA), when we exceed beta we know the move is 'too good' and cut off the rest of the search. Since some of the search is cut off we do not know what the actual evaluation of the position was. All we know is it was atleast 'beta' or higher.

    Alpha Evaluation (HASH_ALPHA), when we do not reach up to alpha. We only know that the evaluation was not as high as alpha.

    The exact flag is applied if the evaluation was between alpha and beta.

    The beta flag is applied if the evaluation caused a cut off, i.e. exceeding beta, this is also done if the null-move causes a cut off.

    And the alpha flag is applied if the evaluation never exceeded alpha.

    I will explain how this is used further down.

  • Best move

    This is also pretty straight forward. Here we store the best move for the position. We do not always have a best move to store, in that case we leave the field empty, as long as we know this happens it is not a problem.
In Medioce I fill the hastable with an internal hashentry class looking like this:
private class Hashentry
{
public long zobrist;
public int depth;
public int flag;
public int eval;
public int ancient;
public Move move;

public Hashentry(long zobrist, int depth, int flag,
int eval, int ancient, Move move)
{
this.zobrist = zobrist;
this.depth = depth;
this.flag = flag;
this.eval = eval;
this.ancient = ancient;
this.move = move;
}
}
As you can see I also have a field called 'ancient' there. This is used to sort out old entries that are of no use anymore, I will explain how to use it below.

Replacement Schemes

If we want to store a position that already exists in the transposition table we need to make a decision. We use a replacement scheme to decide wether to keep the old entry or replace it.

There have been a lot of research on this subject, here is the short version.
  • Always replace

    Using this scheme we always replace an entry, we do not care what the old entry was holding.

    This scheme works quite ok, and is very simple to implement.

  • Replace by depth

    Here we replace if the new entry has greater depth than the old entry. The idea is that an entry with a greater depth used more time to get to the evaluation, hence keeping the entry with the greater depth will save more time in the future.

  • Deep + always

    Here we store two entries at every position, the first entry being 'replace by depth' and the second 'always replace'. So if the new entry had greater depth, we put it in the first entry. If it had smaller depth we replace the second entry without looking at it.

    Testing has shown this is the most effective scheme, it is a tad more complicated to implement though


There are also two schemes called 'old' which never replaces an entry (opposite of always replacing), and is quite useless. And 'big' which instead of looking at the depth looks at the actual size of the subtree, this takes keeping track of the subtree and is quite complicated, but it is supposed to be fast (even faster than replacing by depth).

Mediocre uses the 'replace by depth' scheme. I might implement a two level transposition table (depth + always) in the future, but for now only looking at depth works fine.

Collisions

When storing a position in Mediocre I do not check if the new entry is for the same position or another one (i.e. two different positions hashed to the same index). I simply check if the depth is greater in the new position, and if it is it replaces the old, even if it is a totally different position.

However there are ways to fill the hashtable better.

If you have two different position hashing to the same index you can store the second position in say index hashkey+1, and when you look for a position you first look at the index 'hashkey' and if another position was there you look at index hashkey+1.

You can also have more elements at the same index, this is called 'buckets'. So when looking at an index you check 'bucket' 1 (element 1) first, and then bucket 2 and so on. If all buckets get filled up you need to start replacing.

If you have too many buckets, or use to many extra keys (e.g. hashkey+100), searching for a position takes too much time since you will have to look at every possible spot before determining the position did not exist.

Four possible positions for every index is what most people use I believe.

Remember you should only have one entry for a particular position stored in the table, the buckets (or hashkey+1) are used for different positions hashed to the same index.

This way you fill the hashtable more effectively.

I will probably implement this in the future.

Ancient nodes

Since Mediocre only replaces an entry in the transposition table if its depth is greater than the old entry, the hashtable will sooner or later be filled up with deep results from old searches that probably never will occur on the board again.

There are different ways to handle this. One obvious way is to clear the transposition table after each or every couple of moves.

But by doing that you might lose transpositions that could have been used on later moves.

Instead I use an 'ancient' field in the hash entries. In the Mediocre-class I switch a 'master ancient'-boolean every time I make a move, and if an entry has a different ancient-boolean than the 'master ancient' it is automatically replaced. This way half of the time old nodes will be replaced.

This is a crude way of doing it and I will develop it further in future releases.

New way of collecting the pv

Since we now store all our positions in the transposition table we can extract the principal variation from it.

When the search is finished we lookup the position from where the search started and add the best move from the hashtable, the we make the move on the board and get the move from that position and so on until the expected number of moves have been found.

After we are done we unmake all the moves on the board and we have our principal variation.

We have to be careful that everything is right when doing this, there are some nasty bugs that can occur, like I illustrated in my last post.

Draw detection

I threw away my old crude fen-string draw detection and replaced it with a new zobrist key based detection instead.

For now it works exactly the same, but instead of generating and storing the slow fen-strings I store zobrist keys in a small hashtable, and if I detect a repetition I return 'draw' as evaluation.

This only takes care of repetitions where the position has occured once in the game history and once in the search, so repetitions that occur only in the game tree are not considered.

I will improve this in future releases.

Moving on, finally!

I can finally move on to more interesting things. Like improved evaluation, and take alook at internal iterative deepening, and futility pruning (again). Also a in check extension is sorely needed. We will see where I start.

[Other] A good night's sleep is all it takes

Yesterday I was just about to start writing the transposition table guide, after having sorted out a few more bugs and it all seemed to work nicely. So I started a tournament between v0.12b and Mediocre with transposition tables in the background, and started typing.

And in the first game, just after I had typed the first paragraph in my guide, ANOTHER bug appeared out of nowhere.

It was in the following position:

Mediocre v0.12b is white, to move, and Mediocre with transposition tables black, and after:
a3   Nxe4
Bxe4 Nf6
Bd3 Nd7
axb4 f5
Bxf5
Mediocre with transposition tables crashed. And also Nd7 looks like weird move since it just hangs the pawn on b4.

So back to bug hunting again. :(

After a while I realized the crash originated from my method of extracting the principal variation from the transposition tables.

After the move 'Bd3' Mediocre with transposition tables calculated with Nd7 followed by Bxe4 which of course is not possible in the position (there is no black piece on e4 after the moves).

Calculating with transposition tables turned off did not have the problem, so the Bxe4 had to come from the transposition table. Then the pv extraction method played it on the board (to find the next move in the line) and when unmaking the move a black knight appeared on e4 out of nowhere (since the unmake-method puts back whatever piece that was captured, and Bxe4 apparently had a black knight in its capture field).

And then after a couple of moves v0.12b plays Bxf5, so Mediocre with transposition tables crashes since in its internal board there is a knight on e4, making Bxf5 illegal.

Now I tried a bunch of different ways to get around the problem, thinking it was just an update problem of some sort that did not interfere with the actual calculation. But nothing worked.

I then woke up this morning and before I turned on the computer I realized what the problem was, and exactly where I had to make a change in the code. :)

The problem is in the Zobrist keys (even though I did extended testing on those).

The following two positions should not return the same Zobrist key:

And they did not if inserted separately with fen-strings. But if the first position was inserted with a fen-string and then the sequence:
Bxe4 Nf6
Bd3 Nd7
was played (which ends up in the second position) the Zobrist keys magically matched. Which they should not!

The problem is, in my make and unmake move methods I only update the zobrist with the piece moving if it is a capture. Just like I update the board array.

A piece on d3 capturing a piece on e4 is in the board array done with setting 'd3' to empty and 'e4' to the piece moving. Setting 'e4' to the piece moving automatically replaces whatever piece was there before and we do not have to worry about it.

But a Zobrist key does not work that way, you have to 'remove' the captured piece as well by updating the Zobrist key with its position just like you would remove the moving piece from 'd3'.

Hopefully there are no more bugs now, and I can go on to writing my guide and releasing Mediocre v0.2b.

Hopefully... :)

Jan 24, 2007

[Other] Better but some bugs

I ran a few games between Mediocre with transposition tables and Mediocre v0.12b, the new Mediocre won pretty much every game except the ones it forfeited due crashing or playing illegal moves. :)

It searches about a ply or two deeper in every given middle game position, and much deeper in end games.

There are still some big bugs to be sorted out, but they are atleast getting fewer.

The repetition draw detection in search tree is a hassle and I will wait with it a bit, atleast until after I have written the new evaluation. However the draw detection with positions from the game history works without problem, with new zobrist keys instead of the slow FEN-approach I had before.

Jan 22, 2007

[Other] Draw repetition left

After taking a long look at King's Out's implementation of transposition tables I finally understood what I had to do to get everything working correctly in Mediocre.

Man that was a hard piece of code to write... All in all 10 lines or so in the alpha-beta method, and almost two weeks to get them working right. :)

The speed gains are noticeable but not enormous. But with the transposition tables as a foundation there are a lot of optimization that can be done.

Where it really made a difference is in the endgame though. In the null move example a couple of posts back Mediocre can now reach 16 ply in under a second, while without transposition tables it reaches only 9 ply in the same time.

Now I just need to replace my crude repetition detection and possibly take another look at the replacement scheme the transposition table uses (uses depth replacement now).

[Other] Progress

The implementation of Transposition tables are taking a whole lot of time, I am struggling with just about everything. :) From wrong values in the table, to incomplete principal variations, to weird cut offs and wrong evaluations.

Yesterday I finally got the basics working without bugs. Mediocre stores the positions in the transposition tables and recognizes repeated positions in the search. It also searches the hash table move first in every alpha-beta search.

What is left is using non-exact values (i.e. values from failing high (beta cut off) and failing low (not reaching alpha). These values can not be used as exact values since they are only estimated (we did not search all moves in the line).

When trying to use the non-exact values I get weird results, but I am homing in on the problem atleast. It should have something to do with the positive and negative values received from the evaluation based on who is moving.

Anyway I am getting closer. :) You can start looking forward to a big guide to transposition tables as soon as I am ready.

Jan 16, 2007

[Other] Null move reminder

I ran into trouble in the following position when trying out the transposition table:

It is white to move and obviously we want the engine to move the pawn.

With my current evaluation this position is evaluated to +100. Since white is a pawn up and I do not give bonuses for passed pawns or king positioning and such yet.

I do however give a bonus for a h/a-row pawn on the 6th rank, and a bigger bonus on the 7th rank. This is just a crude solution to help the engine realize advancing the pawns is a good thing if all else is equal. I will of course ellaborate a lot on this when I get to expanding the evaluation.

Anyway, in this position the engine should see the pawn getting to rank 6 in 5 plies. To rank 7 in 7 plies and to rank 8 in 9 plies.

But the evaluation at the different depths looked like this:
Ply Eval PV
1 100 Kb2
2 100 Kb2 Kg3
3 100 Kb2 Kg3 a3
4 100 Kb2 Kg3 a3 Kh2
5 100 Kb2 Kg3 a3 Kh2 Kc1
6 100 Kb2 Kg3 a3 Kh2 Kc1 Kg1
7 100 Kb2 Kg3 a3 Kh2 Kc1 Kg1 Kb2
8 100 Kb2 Kg3 a3 Kh2 Kc1 Kg1 Kb2 Kf2
9 120 a4 Kg3 a5 Kh2 a6 Kg1 Kb2 Kf2 a7
10 900 a4 Kg3 a5 Kh2 a6 Kg1 a7 Kf2 a8=Q Kg1
11 900 Kb2 Kg3 a4 Kh2 a5 Kg1 a6 Kf2 a7 Kg1 a8=Q
Clearly something is wrong.

The engine does not see the advance to 6th rank on the 5th ply nor does it see the queening of the pawn on the 9th ply, but on the 9th ply it does see the reaching of the 7th rank. Only at 10 ply does it see the queening.

After some testing and logical thinking I came to the conclusion null move pruning was the problem. And by disabling them I got this analysis instead:
Ply Eval PV
1 100 Kb2
2 100 Kb2 Kg3
3 100 Kb2 Kg3 a3
4 100 Kb2 Kg3 a3 Kh2
5 115 a4 Kg3 a5 Kh2 a6
6 115 a4 Kg3 a5 Kh2 a6 Kg1
7 120 a4 Kg3 a5 Kh2 a6 Kg1 a7
8 120 a4 Kg3 a5 Kh2 a6 Kg1 a7 Kf2
9 900 a4 Kg3 a5 Kh2 a6 Kg1 a7 Kf2 a8=Q
10 900 a4 Kg3 a5 Kh2 a6 Kg1 a7 Kf2 a8=Q Kg1
11 900 a4 Kg3 a5 Kh2 a6 Kg1 a7 Kf2 a8=Q Kg1 Kb2
Now it correctly spots the 6th rank advance on the 5th ply, and the queening on the 9th.

The reason for this is null-moves assume moving is an advantage. But since there is nothing black can do to improve his position it is not an advantage in this position.

What happens is when we try a null-move black can not improve his position and we assume the line is too strong. While it in fact is exactly the same (+100).

Null moves will work better in positions like this if we have more evaluations. Let us say black would get a higher score if he moved his king towards the pawn. If that was the case we would not cut off the line and the 'a4' move would not disappear in the cutoffs.

However as I said before, we should not use null moves in the end game even if we do have better evaluation (atleast not null moves in this form) since the risk of zugswang (explained earlier) is too great.

Well, I just wanted to share some insights I am getting from implementing the transposition table. It is really important to understand the search of your engine in order to get it working correctly. Especially how to use alpha and beta values.

Jan 15, 2007

[Other] A little update

I am as you know currently working with the Transposition Table. It is some hard work to get it all working especially since I am going to rewrite the way I handle the principle variation as well.

I am taking it a bit slow since bugs in the hash tables are nasty and can pop up when you least expect it. One game the engine is playing perfectly and the next it looses a queen for nothing.

The supercomputer Hydra did such a mistake in a tournament a year or so back. Sacrificing a piece for nothing and its evaluation did not drop until the next move when it realized its mistake. That was due to a hash table bug.

I am also configuring Eclipse to get it to work as I want (black text on white background hurts your eyes after 10 hours :). The first experiences with it has been rather nice and I will probably keep it. Though it does take some time to get used to.

Jan 14, 2007

[Other] VIM vs. Eclipse

I have always used VIM for developing. The main reason being its high configurability, you can do pretty much anything with it. But it does take some time to get it setup right.

Also it does not create any weird code or files that you have no control over.

While it suites me perfectly there are some features I do miss. So I took a look at Eclipse.

It has some very interesting features and from what I have seen so far it seems like you have good control over what it does to your program.

I will be trying it out for a while and see if it is worth doing the switch. So the next version of Mediocre will probably look a bit different, with some new folders that Eclipse uses.

It will probably take a while to get comfortable with it so wish me good luck. :)

Jan 12, 2007

[Other] Lot of work with Zobrist keys

While being a pretty straight forward concept there are a lot of things that can go wrong with the Zobrist keys. Not the basic implementation, but integrating it to the makeMove and unmakeMove methods.

It was a lot of hard work to get it to work right. The main problem is even a tiny coding error leads to a completely different key, and unless you catch it with testing where you actually see the keys you will end up with a flawed hash table later on.

I wrote a whole set of tests to try every eventuallity. I caught things like castling long for black, and promoting to bishop for white returned wrong keys.

If I had not caught those at this stage, the engine could start acting weird once the hash tables got implemented and you would have no idea where to look.

The way I tested was setting up a position with a FEN-string and printing the Zobrist key, then making and unmaking a move and see if the key matched after the moves.

This way you catch both making and unmaking errors as well as getting a simple way of checking the validity of the keys (instead of inserting the new position after a move and generating a new key).

Well, time to put it to use in the transposition table.

Jan 11, 2007

[Guide] Zobrist keys

Before starting to work with the transposition table (which will be represented as a hash table, more about that later) we need yet another way of representing the position on the board.

We will be using a routine called Zobrist keys for this.

Why another representation?

With Zobrist keys implemented we will have three ways of representing the board in Mediocre. A Board-object, a FEN-string and a Zobrist key.

Each of these serves a special purpose:

The Board-object is the main structure used by the program. Not only does it hold the position but it generates moves, makes moves, and more. We can not really use this for any sort of indexing or comparing without many slow operations.

FEN-strings are mainly used for user interaction (inserting and outputting positions), although I have used them for draw detection and history storage up until now they are not suited for this since they can not be hashed or updated easily. As pointed out to me the FEN-string method currently takes about 35% of the cpu time, this is due to the repetition detection and it proves how very bad the FEN-strings are for this.

Zobrist keys will be used in the transpositions table and for repetition detection. Since a Zobrist key only is a bunch of numbers we can not use them to describe a position to the user.

But since every position has its own unique bunch of numbers, they can be used to compare and store positions with a very high efficiency.

They are perfectly suited for hashing since every change in the position generates a completely different set of numbers. A FEN-string for example would look almost the same after a move which could cause collisions in the hash table. (more on this when I explain transposition tables).

They are also easy to update so we do not have to generate a whole new key every time we make a move. More about this below.

How to create a Zobrist key

A Zobrist key is a 64 bit number that represents a position on the board. In Java the 'long' type is 64 bits (8 bytes) so that is what we will be using.

64 bits is enough to create a unique enough value for every position. I say unique enough because it is not really unique, there are so many positions in chess that even a 64 bit number can not represent them all. There will be occassions when two different positions get the same value, but this is so rare that we do not have to worry about it.

First we need a structure that we will fill with randomly generated numbers. The structure I am using looks like this:
long[6][2][120] PIECES    // [piece type][side to move][square]
long[4] W_CASTLING_RIGHTS // Four different castling setups
long[4] B_CASTLING_RIGHTS // both ways, short, long and none
long[120] EN_PASSANT // En passant
long SIDE // Used for changing sides
Then we fill every spot with a random number. Like this:
Random rnd = new Random();

SIDE = rnd.nextLong();

for(int i = 0; i < 4; i++)
{
W_CASTLING_RIGHTS[i] = rnd.nextLong();
B_CASTLING_RIGHTS[i] = rnd.nextLong();
}
And similar for PIECES and EN_PASSANT. While EN_PASSANT really can only occur on 16 squares (as mentioned earlier), since I do these two in the same loop I might as well fill random numbers for all real squares. Just easier that way.

So now we have a bunch of arrays with random numbers. Great, so what?

The trick is if we have a random number and XOR (explained below) another random number, we get a third seemingly random number. By XORing all random numbers from pieces, en passant and castling rights we get a unique key for the position.

This is done something like this:
long zobristKey = 0;

for(int index = 0; index < 120; index++)
{
int piece = board.boardArray[index];
if(piece > 0) // White piece
zobristKey ^= PIECES[Math.abs(piece)-1][0][index];
else if(piece < 0) // Black piece
zobristKey ^= PIECES[Math.abs(piece)-1][1][index];
}

zobristKey ^= W_CASTLING_RIGHTS[board.white_castle];
zobristKey ^= B_CASTLING_RIGHTS[board.black_castle];

if(board.enPassant != -1) zobristKey ^= EN_PASSANT[board.enPassant];
if(board.toMove == -1) zobristKey ^= SIDE;
We need to distinguish white to move and black to move, since they are two different positions even if all pieces, castling rights and en passant are the same. We do this by XORing the SIDE number, this only has to be done if black is to move, else we use the first number we get.

The ^= operator XORs the random number from the array into the zobristKey. The XOR (exclusive OR) is a bitwise operator just like the & (OR) operator explained earlier. But instead of setting a the bit to 1 if either of the bits are 1, it sets it to 1 only if one of the bits is 1.
1 & 1 = 1
1 & 0 = 1
0 & 0 = 0
1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 0 = 0
We really do not have to know this, all we need to know is if we XOR the number a with b we get a third number c.

But the real trick is if we do the XOR operation again we get the initial number back.
a ^ b = c
c ^ b = a
This is in practice with Zobrist keys used to remove pieces on the board. More in the next section.

Anyway, after doing all these operations we now have our unique 64 bit number that represents our position.

Updating the key

Let us say we have a Zobrist key for a position and we want to make white move 'Ra2a3'. We obviously do this with the makeMove()-method in the Board-class, but we can add lines there looking something like this:
zobristKey ^= Zobrist.PIECES[3][0][16];
zobristKey ^= Zobrist.PIECES[3][0][32];
The first line XORs the random number we have for [rook][white][index], since we already had a white rook on index 16 this will 'remove' it and then we insert a new rook on index 32 with the next line.

And similarly when unmaking the move.

If we do this for every move, and castling/en passant changes. We will always have an updated zobrist key for the position.

Showing what we get

Here is an example of creating and updating a Zobrist key.

I am going to take the start position, generate a Zobrist key, then make the move, look at the new key and unmake the move to make sure we get the first key back.

Also I will manually change the Zobrist key to see that it works the same way as making the move.

The code:
board.setupStart();

System.out.println(Zobrist.getZobristKey(board));

board.makeMove(move); // Making the move 'a2a4'
System.out.println(Zobrist.getZobristKey(board));
board.unmakeMove(move);
System.out.println(Zobrist.getZobristKey(board));

System.out.println("---");

System.out.println(Zobrist.getZobristKey(board));
long key = Zobrist.getZobristKey(board);
key ^= Zobrist.PIECES[5][0][16];
key ^= Zobrist.PIECES[5][0][48];

System.out.println(key);

key ^= Zobrist.PIECES[5][0][48];
key ^= Zobrist.PIECES[5][0][16];

System.out.println(key);
The result is this:
2809723212531837306 // Inital position
6377746370581267278 // After a2a4
2809723212531837306 // Initial position (should be same)
---
2809723212531837306 // Initial position (should be same)
4051561200414578875 // After manually inputting a2a4
2809723212531837306 // Initial position (should be same)
Notice how we in both cases get back to the inital key.

We get a different key after 'a2a4' in the both cases. This is because I have not considered side to move changing and the en passant square. If I XOR these manually as well we will get the same number.

If we exit the program and rerun the exact same code we would get different numbers, since they are generated randomly at startup. This of course expected, and as long as we use the same random numbers during the search the engine will always recognize the positions. Though if we changed the random numbers in the middle of the search the engine would get confused.

Here is another example showing that different move sequences lead to the same key.
board.setupStart();

key = Zobrist.getZobristKey(board);
key ^= Zobrist.PIECES[5][0][16]; // Making the move a2a4
key ^= Zobrist.PIECES[5][0][48];

key ^= Zobrist.PIECES[5][0][17]; // Making the move b2b4
key ^= Zobrist.PIECES[5][0][49];

System.out.println(key);

board.setupStart();

key = Zobrist.getZobristKey(board);
key ^= Zobrist.PIECES[5][0][17]; // Making the move b2b4 first
key ^= Zobrist.PIECES[5][0][49];

key ^= Zobrist.PIECES[5][0][16]; // Then a2a4
key ^= Zobrist.PIECES[5][0][48];

System.out.println(key);
The output will be something like:
4594401896990620738
4594401896990620738
So we reach the same key with different move orders. This is called a transposition and I will discuss this in my next post.

This turned out to be a rather long post about an easy subject. You really do not have to understand everything about XORing, just consider it as magic and it will work. :)

[Other] A way to show games

I have been looking for a small simple applet or flash program to view games I want to show.

There are some big advanced ones with commentary and multiple games, but they simply will not fit on this pages.

The best one I found so far is located at http://chess.maribelajar.com/chesspublisher/ and is very easy to use. Unfortunately the background is white so it will look really bad. :) But atleast it is a simple way of showing games.

To try it out here is a game Mediocre won against the strong java engine King's Out. All luck of course, but still. :)

[Other] Moving on

I finally got the futility pruning working as it should, though the gains seem very limited at the moment.

I am not quite sure what causes this. Probably a combination of alot of things, like inCheck checks being too costly and the evaluation being very fast as it is.

Perhaps down the line when other things get optimized and extended we will see more benefits from futility pruning.

But for now I am not going to use it. It introduces a risk of missing combinations for very little gain (atleast in Mediocre's current state).

So now it is time to move on to a big project. The hash tables. With zobrist keys and transposition tables and more.

Jan 10, 2007

[Guide] Futile attempts with futility pruning

In short futility pruning prunes nodes that are so bad that they most likely can not compete with the principal variation.

Names of the depths

Firstly lets get a few terms clear. These are names of different depths in the search.

Root: This is where the first moves for the side to move are generated and searched one by one. If we do a 5 ply search, this will be called depth=5 (since that is what we call alpha-beta with).

Horizon: This is when the depth is reached and we call quiescent search. So we call it depth=0, since that is what we have when quiescent search is called.

Frontier: This is the depth before the horizon. Depth=1.

Futility pruning

Futility pruning is done at the frontier nodes (depth=1). If we are at a frontier node first we call the static evaluation and if that evaluation + a margin (usually the value of a minor piece) is not better than alpha. We know that this node has no chance of beating the alpha even if we search one ply more.

So we return the evaluation (or call quiescent search) and skip the last ply.

We do not want to do this if the last move was a capture or if we are in check or if the next move is a checking move. If any of these cases are true the position is too dynamic to be pruned and we risk missing something important.

Extended futility pruning

Works exactly like futility pruning but is done at pre-frontier nodes (depth=2) and the margin is bigger (atleast the value of a rook).

The margin needs to be bigger since we are pruning 2 plies here and the risk of missing something is much greater.

Razoring

Pretty much like futility pruning, but is done at pre-pre-frontier nodes (depth=3). The margin needs to be about the value of a queen here. And instead of returning the evaluation or calling quiescent search we reduce the search depth with 1 ply.

So we actually do not prune the entire branch but only shorten it a bit.

Problems in Mediocre

I have tried implementing this for hours but I am apparently doing something wrong. The theory is so simple that it should not really be a problem.

I am getting weird results. With some settings I get a decrease in performance, that is the engine takes longer time to reach the search depth. This should not be possible since all we do is remove searches from the tree and I can not see how that would slow down the calculation.

With other settings I get a massive performance improvement, but get extremely weird principal variations. Sometimes the engine does not return a full principal variation line, and sometimes it returns a line with black moves where it should be white.

When trying to play games with these settings the engine blends perfectly good moves with horrible mistakes. So horrible that it can not possibly be the result of a cut ply.

It can take a protected pawn with the queen and in the principal variation expect the queen to be taken, but still evaluate the position as equal.

I am leaning towards letting this go at the moment and start with the hash tables.

But since I am too stubborn for my own good I have a feeling I will keep working on this until I get it to run.

[Guide] Trying out advanced killer moves and history heuristic

I have been tweaking my killer moves a bit and tried out the history heuristic.

Advanced Killer Moves

Up until now the killer moves have been replaced every time a new cutoff is done. That is alot of mindless replacing.

I am currently trying out a scheme that keeps track of every move on the board if it causes a cutoff, and increments a count each time it does. If any move were to surpass the current primary and secondary killer moves in number of cutoffs, it takes one of their spots. We keep track of this with a three-dimension array like this:
int[][][] everyKiller = new int[100][120][120]
The first dimension is for what ply the killer move exists on, the second is 'fromIndex' and the third is 'toIndex'. Remember that our 0x88 board has indexes from 0 to 120.

Every time a move causes a cutoff we increment its place in the array. So if the move Ra1xa8 caused a cutoff at ply 5 we increment the spot everyKiller[5][0][112] by one.

Then we check if the move has a higher value than either of the current primary or secondary killer moves, if it does we replace one of them with it.

This makes for a more intelliget selection of killer moves. I can not say I noticed any drastic improvement in performance, but I only tested it on a few positions and it did not cost any extra time either. I do think it is for the better however, especially at higher depths when the statistics get a bit more stable.

History Heuristic

The history heuristic is very simple to implement and works similarly to the advanced killer moves. The difference is we do not keep track of what ply the move exists on, or primary/secondary moves.

This is done by using a two-dimension global array that symbolizes all moves. The first dimension is 'fromIndex' and the second 'toIndex'. Like this:
int[][] historyMoves = [120][120]
When a move causes a cutoff in the alpha-beta search we increment its place in the array like this:
historyMoves[move.fromIndex][move.toIndex]++;
The numbers collected in this array are then used to 'award' ordering points in the move sorting. If a move has a high value in the history array it will be searched earlier than a move with a low value.

I have read about engines keeping primary and secondary history moves, but using the values to order all moves seems more logical.

When trying out the history heuristic I did not notice a big difference on lower plies, of course that is not to be expected since the history array is barely filled and the calculation time is so low that we can not expect any vast improvements.

But when I searched 4 different positions to depth 6 the difference was huge. 1 minute 4 seconds with history heuristics turned on, and 2 minutes 3 seconds with it turned off.

It seems the history heuristic is well worth the small trouble.

Jan 9, 2007

[New Version] v0.12b - Uci support, time management

Changes:
  • Time mangement added
  • UCI support added
  • Machine vs. Machine in winboard should now work
  • Added support for the 'force' command in winboard
  • Fixed a bug conerning en passant, perft values are now correct
  • Perft and Tests classes were added, these are best called in the new line mode
  • Calling Mediocre without argument now enters a simple line mode
  • Added a few parameters to Engine.search() to allow uci/winboard thinking, fixed depth and time management
  • Added setupStart() to Board, which sets up the initial position
And a big thanks to Yves Catineau for helping with the UCI support.

Note: The readme.txt was updated to properly describe installing Mediocre in WinBoard. There are also two different .bat-files now, one for winboard and one for uci.

mediocre_v0.12b

[Guide] Time management

In order for the engine not to run out of time, and to think as deep as possible with the time given, we need a way to determine how long to think on each move.

Allocate time

To start off we need to determine how much time to allocate on each move.

We could keep an internal timer to keep track of the time, but both the WinBoard and UCI protocols submits the time left for both sides after each move. So we have that information for free.

See the corresponding protocol for how to receive that information from the interface. (or look in my code once I release the next version)

My method to determine how much time to use looks like this:
// Use 2.25% of the time + half of the increment
int timeForThisMove = timeLeft/40+(increment/2);

// If the increment puts us above the total time left
// use the timeleft - 0.5 seconds
if(timeForThisMove >= timeLeft)
timeForThisMove = timeLeft -500;

// If 0.5 seconds puts us below 0
// use 0.1 seconds to atleast get some move.
if(timeForThisMove < 0)
timeForThisMove = 100;

return timeForThisMove;
I take 2.25% of the total time left and give a bonus if the time controls includes an increment (extra time after each move). To make sure we do not run out of time due to the increment bonus I make a check to see that we do not allocate more time than the total time left.

This seems to work ok in most situations, but I am sure some tweaking can be done.

Hard stop

As I mentioned in an earlier post it is not enough to check for allocated time being up after each iteration of the iterative deepening loop.

Let us say we allocated 2 seconds for this move, and after searching 4 plies we have used 1.9 seconds. Since the time is not up we start searching the next depth, this search could take say 5 seconds, making the search run for 6.9 seconds instead of 2.

We need a way to stop the search even if we have started the alpha-beta sequence.

What I have done is add the following code at the top of the alphaBeta()-method:
nextTimeCheck--;
if(nextTimeCheck == 0) // Time to check the time
{
nextTimeCheck = TIME_CHECK_INTERVAL;
if((System.currentTimeMillis() - startTime) > timeForThisMove)
{
stopSearch = true;
return 0;
}
}
I used this idea from the King's Out engine but it is a pretty basic concept.

Every few alphaBeta() calls we check if the time is up, if it is we immediately return 0 and set stopSearch to true.

When stopSearch is true we do not make any more searching in the alphaBeta().

Once we get back to the iterative deepening loop if stopSearch is true, we break the loop and discard any results the last alpha-beta call might have produced.

This is called a hard stop and allows us to break the recursive alphaBeta-calls very quickly.

One more check

While the hard stop allows us to stop searching when the time is up, we still have a problem.

If we allocated 30 seconds on the move, and searching up to 7 ply used 16 seconds so far, we would go to the next depth and start searching. If the 8 ply search takes 35 seconds we would break it with the hard stop at 30 seconds thus wasting 14 seconds on a search that we discarded.

It is impossible to know exactly how long a certain depth search will take, but we can estimate it.

There are probably ellaborate ways to do this, but what I did was assume that the next search depth will take atleast twice as long as the previous.

So before going to the next depth I make a check to see if we have enough time left to search for 2 times the last depth's time. Like this:
if((System.currentTimeMillis() - startTime) * 2 > timeForThisMove)
break;
In the example above where we allocated 30 seconds and a 7 ply search took 16 seconds, we would check if 16*2 is within the allocated time before starting the next search. Since 16*2>30 we would not start the next search and simply return the 7 ply result.

Nuances

There are plenty of things to do to optimize the time we use on moves. Complicated middle games migth require a bit more time, and if we noticed a mate threat in the last search it could be worth searching for a bit longer just to make sure.

These are things to consider, but the basic setup I explained above works well.

Edits:
2007-01-09 - Changed the increment bonus example to work with milliseconds instead of full seconds

[Guide] Communication Protocols

I have already touched this subject a few times. Here is a more thorough explanation.

What it does

Chess communication protocols are used to help chess engines communicate with an interface.

The protocol sends information about the game on a certain form, and receives moves and information from the engines based on given standards.

The main advantage is of course that you only need one interface to run several different engines. As long as they support the protocol used you will be able to run them.

The two main protocols

There are two main chess communication protocols. WinBoard and UCI.

WinBoard (or xboard, they are the same) was developed by Tim Mann and is probably the most common protocol, in recent years however the UCI protcol developed by Rudolf Huber and Stefan Meyer-Kahlen (creator of the Shredder engine), has gained ground.

The specifications can be found here:

UCI specifications
WinBoard specifications

How they work

The main principle is the same for both protocols. The interface (be it winboard or uci compatible) sends strings with information, and handles responses from the engine.

To be able to catch the information sent from the interface you need a loop that looks for input. In Java it could look like this:
BufferedReader reader =
new BufferedReader(new InputStreamReader(System.in));
for(;;) // Endless loop
{
String command = reader.readLine();

if(command.equals("something"))
{
doSomething();
}
}
This should be familiar to anyone who has ever written a Java program that accepts input.

Sending information to the interface is done with the System.out.print command.

The format of the input and output is specified in the specifications of the protocol used.

For example when the user (could be a player or another engine) makes a move, WinBoard will send the string:
"usermove e2e4"
When the engine receives this input it should make it on the board and start thinking, and then send a response like this:
System.out.println("move e2e4");
This tells the interface that the engine want to make the move.

Using UCI it works a bit differently. When the user makes a move a string on this form is sent:
"position startpos moves e2e4 e7e5 g1f3"
or
"position fen [a fen string] moves e7e5 g1f3"
The 'startpos' indicates the game started from the initial position, and the moves following 'moves' are the moves played since the startposition. If it is a fen-string instead it indicates that the game probably started from some other position.

When the engine receives this line it should setup the position (be it start position or the fen-string) and play the moves on the internal board.

The 'position' string from UCI does not tell the engine to start thinking or responding. This is done with the 'go' command. So when the engine receives 'go' it should start thinking on the position currently on the board, which in a normal game will have been received in a 'position'-string right before the 'go'.

And then send its move using:
System.out.println("bestmove e2e4");
There is a 'go' command in WinBoard as well, but this is only sent to make the engine leave 'force' mode after setting up the board, or if we want the engine to play white from the initial position.

If the engine is told to go to 'force' mode by WinBoard it should register moves on the board, but not respond or think.

And much more

There are a number of other commands both for WinBoard and UCI, but I leave that to you to read about in the specifications.

I urge you to read the specifications carefully. Make sure your engine does exactly what they say, since the interfaces will assume it does and weird things can happen if you try to do it differently.

Which to choose

As you can see there are subtle differences in the two protocols. Which protocol to use is a matter of taste. You have to consider what interfaces you will be using and decide which one suites you the best.

A tip is to choose one protocol and stick with it. Maintaining both is twice the work, not only do you have to be able to handle different inputs, but you also have to send thinking lines and moves in two different ways.

On the other hand your engine will run on pretty much any interface if it supports both.

[Other] A fun game

After finishing with the protocols I decided to work a bit with the time management. The next version of Mediocre will have a ton of changes; uci support, time management, a bunch of new winboard/uci commands supported, command line and more. But nothing that actually improves the calculation, although time management will help winning games of course.

I will go through what I did to the time controls in my next post. And then say a word or two about the WinBoard and UCI protocols.

Before that though here is a fun game Mediocre played against himself with 1 minute time controls (which he handles exceptionally well with the new time mangement I might say).
 1.d4 d5
2.c4 c6
3.Nf3 Nf6
4.Nc3 e6
5.Bg5 dxc4 (end of opening)
6.e4 b5
7.e5 h6
8.Bh4 g5
9.exf6 gxh4
10.Ne4 Nd7
11.Ne5 Nxf6 {(Nxf6 Nxc6 Bb4 Ke2) +0.85/4 0}
A typical example of the horizon effect. Black pushes back the horizon just enough with the check to miss the capture of his queen. White did not see the queen capture either, he also only saw the bishop checking. Since Mediocre's quiescent search only calculates captures, an inbetween check can be devastating.

On the next move black realizes his mistake. He will not be able to move his queen after Nxc6 since Nxf6 will be check mate with the two knights!
12.Nxc6 Nxe4 {(Nxe4 Nxd8 Bb4 Ke2) -1.88/4 0}
13.Nxd8 Bb4+
14.Ke2 Kxd8
15.f3 Nf6
16.a3 Ba5
17.a4 Rb8
18.axb5 Rxb5
19.Qc2 e5
20.Rd1 Bd7
21.Qxc4 Rxb2+
22.Ke3 exd4+
23.Rxd4 Re8+
White has put himself in a whole lot of trouble, he will have to give back material or be mated. Ke3 is met by Rd2 mate. And Kf4 by Nh5 mate. Quite clumsy by white, but oh so nice. :)





24.Re4 Nxe4 
25.fxe4 Bb6+
26.Kd3 Bb5
27.Kc3 Bxc4
28.Kxb2 Rxe4
29.Bxc4 Rxc4
The rest of the game is a display of poor endgame technique, but it gets the job done. :)
30.Kb3 Rg4 
31.Rd1+ Ke7
32.Re1+ Kd6
33.Rd1+ Bd4
34.h3 Rf4
35.Kc4 Ke5
36.Re1+ Re4
37.Rb1 f5
38.Rb5+ Kf4
39.Kd3 Ba1
40.Kc2 Bd4
41.Kd1 Bc3
42.Kc2 Ba1
43.Kd1 Bc3
44.Kc2 Ba1
45.Kd1 Bd4
46.Kc2 Be5
47.Ra5 Kg3
48.Rxa7 Kxg2
49.Ra6 f4
50.Rxh6 Kxh3
51.Kd3 Re3+
52.Kd2 Kg4
53.Kc1 h3
54.Kd2 Bc3+
55.Kc1 f3
56.Rg6+ Kf5
57.Rd6 f2
58.Rd5+ Be5
59.Kd2 f1Q
60.Kxe3 Qe1+
61.Kf3 Qh1+
62.Ke2 Qxd5
63.Ke1 h2
64.Kf2 Qd2+
65.Kf1 h1Q# 0-1
Considering the poor evaluation algorithm and shallow search depth with the fast time control (4-5 ply on average) I am quite impressed by this game. There are some typical horizon mistakes, but nothing too bad.

Here is the game in .pgn format with full thinking 'comments' from both sides. fungame.pgn

[Other] Frustration

After 5 hours of tweaking and crying and screaming I finally got both the UCI and WinBoard modes to work.

Programming errors mixed with logical errors and lack of knowledge, together with WinBoard acting like a prick. It was not a fun 5 hours. :)

And to top it off blogspot refuses to work with Firefox tonight for some reason.

Anyway, as I suspected the problem with Machine vs. Machine in WinBoard was due to the lack of the force command. It is now implemented.

I also noticed a bug in the line I used to install Mediocre in winboard.ini. My line looked like this:
"java Mediocre x" /fd="[path]"
This allows spaces in the path. But the /fd command seems to ruin the paths to the other engines in the list.

The easiest way to put a Java engine in the winboard.ini is to use:
"java -classpath [path] Mediocre x"
But if you have spaces in the path (like I do) you can not write it like that since any quotation marks will ruin the command.

If anyone have any idea how to write that line so it works with spaces in the path, please let me know.

Both the UCI and WinBoard mode now works with setting up positions, playing black and white, and playing Machine vs. Machine matches, in both Arena and WinBoard (and hopefully in any other GUI). They also send thinking output.

What does not work is things like analyze mode, move now, ponder, or any kind of settings sent from the GUI, like search depth or move time.

I find these less important at the moment.

I have also been working on a command line interface which will be mainly used for testing, like perft, divide and test suites. I do not intend to make it possible to play from the command line, that is what we have interfaces for.

Now it is time to move on to working on the actual engine.

Jan 8, 2007

[Bug] Using Arena's opening book

I have had a few reports of people having trouble running Mediocre using Arena. The common theme seems to be Mediocre playing the opening moves and then stops.

Arena has a local opening book feature that it uses for both engines playing. Mediocre currently does not support this! I have not looked into it yet but my guess is Arena sends a 'force' command and then plays the moves from the opening book, and when it is done hands over control to the engine again.

Since Mediocre v0.11b does not support the 'force' command it will have no idea what to do after the opening.

That is atleast one thing I can think off, perhaps there is a problem with setboard as well. Anyways I will look into to it and hopefully I can make it work.

For now you will have to turn off the Arena book in order for Mediocre to play.

[Other] Word is spreading, abit early? :)

Browsing around different chess forums I see word of my little blog is spreading. That is great, it is much more fun to write when you know you have readers. :)

I have also noticed a few platform specific compiles (like .exe-files) of Mediocre is out there. While it is fun people want to spread Mediocre, I can not help to think that it might be a tad early.

Mediocre is in very early development stages and trying to make it run in too ellaborate ways might be unwise. Things like the winboard 'force' command, time controls, takeback, analysis, pondering, are just a few things Mediocre is clueless about at the moment.

Well, I will just continue working with the engine as usual and not worry too much. :)

Hopefully I get all the qwirks worked out eventually.

Jan 7, 2007

[Bug] En passant bug

I was fairly sure my move generation was flawless. But of course it was not. :)

Mediocre ran through most perft tests without trouble, but one caused trouble, the start position.

At depth 5 the number started to differ. 36 moves were not found correctly.

So I did a divide-search like I mentioned in my previous post and I noticed moves were missing from the branches starting with pawn to 'a4', 'a3', 'b4', 'g4', 'h3' and 'h4'.

I started tracking the 'h4' move and ran into the following position:

Black has just played g7g4 and my perft method reported finding 21 moves. The correct number is of course 22 moves, 21 ordinary moves and one en passant. It does not take a rocket scientist to understand where the problem was. :)

So I went and looked in the Board-class and looked up the en-passant generation routine. There I found this line:
if((index-17 & 0x88) == 0 && (index-15 & 0x88) == 0
&& (((index - 17) == enPassant)
|| ((index - 15) == enPassant)))
It is supposed to check if the pawn we are generating moves for can reach the en-passant square on the board.

But the logic is obviously flawed. In words it says "if both the square diagonally to the right and diagonally to the left are on the board, and one of them is the en-passant square, add the en-passant move".

I have no idea what I was thinking when I wrote this, but you might remember another bug I had with this. The en-passant square is -1 if no en passant is available and if we have a black pawn on 'a2' it would think an en passant was available outside the board.

Obviously I messed up the bugfix back then. :) So now I simply changed it to:
if(enPassant != -1 &&
(index+17 == enPassant || index+15 == enPassant))
Since the board should never produce an en passant outside the board, we never have to check for the en passant being on the board. As long as it is not -1.

I have to pick my default values more careful in the future.

All better now

After this fix all perft scores are working like a charm. I have not found a single error in any of the tests I have run. So hopefully the move generation is bugfree for now.

[Guide] Perft scores - validating the move generation

I should have done this much earlier, but here we are.

A perft score is the node count from a plain mini-max search on a certain position. For example the start position at depth 1 has 20 nodes, since there are 20 possible moves (nodes). At depth 2 we have 400 nodes, since for every move white makes black can answer with 20 different moves (20*20=400). And so on.

This is used to make sure our move generation works as it should. Now how should we know how many nodes a certain position is supposed to have at a certain depth? Well you could either count them by hand (I rather not do that :) or use another engine which you know has a correct move generator.

Or you could use validated results available on different web sites. Like Sharper.

Or just a test suite, which is basically a text file with fen-strings followed by the correct results at each depth.

Here are the correct number of moves each depth should return, starting with the initial position:

1  20
2 400
3 8902
4 197281
5 4865609
6 119060324
7 3195901860
8 84998978956
9 2439530234167
10 69352859712417

Those values are correct and if your engine does not return the same figures, something is wrong.

My Perft code looks like this:
System.out.println(miniMax(board, 5));

private long miniMax(Board board, int depth)
{
long nodes = 0;
if(depth == 0) return 1;
Vector moves = board.generateMoves();

for(int i = 0; i < moves.size(); i++)
{
board.makeMove((Move)moves.get(i));
nodes += miniMax(board, depth-1);
board.unmakeMove((Move)moves.get(i));
}

return nodes;
}
As you can see it is a mini-max routine which returns '1' on every leaf of the tree. Every node collects the result, and when the search is done you have the final result which is returned and printed.

If you get a conflicting result, something is wrong with your move generation and you will have to go bug-hunting.

Divide the trouble

If you get a result that differs from the validated amount of nodes at a certain depth you know you have a bug somewhere. But unfortunately the number says nothing about where it might be.

To make it easier you can write a 'divide'-method that instead of just printing the total number of nodes, prints every initial move, and then the number of child moves to it. The output from the initital position could look like this:
Searching with depth 5

Move Nodes
Nc3 234656
Na3 198572
Nh3 198502
Nf3 233491
a3 181046
a4 217832
b3 215255
b4 216145
c3 222861
c4 240082
d3 328511
d4 361790
e3 402988
e4 405385
f3 178889
f4 198473
g3 217210
g4 214048
h3 181044
h4 218829

Total nodes: 4865609
Now you need to compare it to another verified engine with a divide function. Sharper has it and also Roce. I used Roce when I verified my results, just start the .exe-file and write 'help' to get the commands.

When you see a conflicting result for some move, you play it on the board and do another divide-search with one less depth. And so on until you reach depth 1 and you will see all the moves and what move you are missing.

It takes time

Testing deeper depths can take a lot of time. We are talking hours and days for 10 ply searches. This is of course because no part of the tree gets cut off like in alpha-beta searches. And even though we do no kind of evaluation in the end, there are insane amounts of nodes to find (from the initial position 10 plies results in nearly 70 trillion nodes).

You will find any errors you might have eventually so it is well worth it. But I recommend you find some good test suite and run every position to about depth 6. This should catch all bugs with alot less time.

Here is the test suite from Roce.

perftsuite.epd (right click and choose 'Save as' to download the file)

To run the test suite automatically you will of course have to do some more programming or just take the fen-strings from the file and check the results manually. I leave that to you.

[New Version] v0.11b - Null moves

Changes:
  • Null-moves added
  • Added isInCheck() to the engine class (used by null-moves)
  • Move sorting is now done after the mate check to save time
mediocre_v0.11b

[Guide] Null-moves

It is time to describe a very powerful search tool. The null-move.

Minimal search trees

There is a limit to how much you can reduce the search tree using different alpha-beta techniques. These techniques work with move ordering, and different search windows (like stated earlier) to try reduce the nodes needed to be searched. The nodes that are pruned are always verified and have no possible way of beating the current best score.

There is actually is a formula of how much the search tree can be reduced using alpha-beta:

B^(D/2) + B^(D/2) - 1

Where B is the branching factor and D is the depth searched. To get to this minimal tree you need perfect move ordering (always looking at the best move first).

Less than minimal

The minimal tree mentioned above is the limit for how small a search tree can get when every single score is verified as being inferior to the best result, by looking at the exact evaluation.

The only thing we do is cut off nodes (moves) that have no chance of beating the best score since the opponent would never allow it.

However, we could cut off nodes that we have not looked at if they appear to be worse than our best move. This is what null-moves are all about. (and futility pruning, but more about that in a later post)

This would reduce the tree even more, at a certain risk of missing something good. First impressions does not always last. :)

Null-moves

A null-move is another word for 'passing'. It simply means the side to play passes and lets the opponent get a free move (i.e. he is allowed to play two consecutive moves).

Let us start with an example, consider the following position:

Somewhere in the search tree we run into the following line:
1. ...  Qc1
2. Qxc1 [any move]
Even if white passes here (plays a null-move) black can not possibly reclaim the material.




The line could look like this:
1. ...    Qc1
2. Qxc1 Rc8
3. [pass] Rxc1
4. Rxc1
And even though white passed, he is still up a rook.

Obviously black would never allow this to happen, so even if we intended to search this line to 20 plies, we can stop searching here. That is a huge amount of work saved.

That is the basic theory. One side gets a free move, and if it can still not improve its position, the line would never be allowed to happen in the first place.

Putting it in programming terms

In an engine the above scenario would translate into black not being able to reach up to alpha, even though he got a free move.

To make sure black (the side who gets a free move) can not reach up to alpha we still need to do some searching, but we do this with a reduced depth. Instead of doing an ordinary search after the null move, we do it like this:
eval = -alphaBeta(ply -1 -R, -beta, -beta + 1);
The window is minimal since we are only interested if the opponent can reach up to alpha, it does not matter how much worse he is.

The R is how much we reduce the depth, more about this further down.

If the opponent could improve his position after a null-move, we need to do an ordinary search. The line is not bad enough for him.

However if he could not improve his position, we can prune the entire subtree, being fairly certain this line would never be allowed to happen.

This means alot of researching. But since the null-move search is much faster than the ordinary seach, and now and then we get to cut off a huge chunk of the search tree, this results in massive time savings.

The R

In Mediocre I use R=2, that is if we were planning to search the position to depth 10, we only search it to depth 8 when null-moving. This is lightyears faster than the full search (remember that every extra ply adds exponentially to the calculating time).

R=2 is commonly accepted as a good reduction to search a null-move. R=1 is usually too small, making the null-move search too slow. And R=3 is too large, making the null-move too likely to miss tactics.

Some engines use a dynamic R that is larger if the original search depth is large. However using a plain R=2 seems to work very well.

Sample code from Mediocre

Here is how I implemented this in Mediocre.

Firstly we need to handle recursive null-moves. We can not allow a tree with all null-moves since it would result in no moves being played at all.

There are different ways to do this. One is to not allow more than two null-moves in every branch. Another is to not allow two consecutive null-moves, that is how Mediocre handles it.

I did this by changing the alphaBeta() to use a boolean parameter called allowNull. Like this:
alphaBeta(board, ply, alpha, beta, pv, boolean allowNull)
Ordinary recursive calls sends allowNull=true, while null-move searches sends allowNull=false.

This way there will always be a real move between every null-move.

The code added inside alphaBeta() is located right before we start our ordinary move search loop, but after evaluation and mateChecks, and looks like this:
if(allowNull && !usingPreviousLine)
{
if(!isInCheck(board))
{
board.toMove *= -1; // Making a null-move
eval = -alphaBeta(board, ply-1-R, -beta,
-beta+1, localpv, false);
board.toMove *= -1; // Unmaking the null-move

if(eval >= beta) return eval; // Cutoff
}
}

// Continue with ordinary search
The first line allows a null-move if the last move was a real move, and if we are not using our principal variation from the last iteration. We do not want to do null-moves before we have received a first result from our previous principal variation. (maybe we could, but it messes up the code in the sortMoves(), so atleast Mediore does not)

Then we see if the side moving is in check. If he is we can not allow a null-move since the opponent would simply capture the king with his next move.

Now we make the null-move and search with reduced depth (R=2 as mentioned).

Then unmake the null-move.

If the evaluation is higher than beta we can simply return beta here, since we encountered a variation like in the example above. That is the null-move was not enough to help the other side get a better score.

If we do not get a cutoff, we continue with the ordinary search as if nothing happened.

Missed lines

Since we do not actually check every line fully there is always a risk we miss something important that would have happened deep in the search tree. We are essentially moving our horizon closer when doing a null-move search, making it more likely that deep tactics end up beyond it.

This should be a rather rare occurence though, and the speed gains should counter it since we will be able to search to deeper depths to start when using null-moves.

It is possible to avoid missing lines by a more advanced way of determining when to use null-moves. One case would be not using null-moves if there is likely to be a mate on the board. Another, and perhaps most imortantly, if a zugswang situation is likely.

Zugswang

There is one very real problem that occur in positions where zugswang is a factor. Consider the following position:

If white is to move here he will have to either move Kd6 which results in stalemate, or move away from the pawn which loses it and draws the game by material.

If however white could pass here (play a null-move) black would have to play Kc7 and white answers Ke7 and the pawn queens.

This is called zugswang, meaning a side loses if he moves, but will be ok if he could pass.

A null-move search is made under the assumption that having your opponent pass is a huge advantage, huge enough to recover even from horrible moves.

In zugswang positions getting to pass is actually an advantage, and therefore the logics of the null-move search fail.

Taking this into consideration we should never use null-moves in endings with few pieces (especially pawn endings), where there is always a great risk of a zugswang situation appearing.

Mediocre does not recognize endings yet (the evaluation is too simple currently) so he happily plays null-moves even in the endings. This will change once I improve the evaluation algorithm though.

Moving on

The results from null-moves were so impressing and so much fun I will take a look at futuility pruning as well. Which uses a similar scheme.

I will also implement a history herustic which works a bit like killer moves.

After that it is time for the extreme makeover of the evaluation class.

[Bug] WinBoard interface - Machine vs. Machine

Apparently Mediocre is having some trouble playing Machine vs. Machine games in WinBoard. I had not noticed this until it was brought to my attention, since I use Arena to play those games.

It seems to work if Mediocre is the first engine, but not if it is the second, or if Mediocre is playing both sides.

My best guess is this has something to do with the 'force' command which is not implemented in Mediocre yet.

I will keep a close watch on this, and hopefully it goes away once 'force' is implemented.

[Other] Fun with null-moves

I have implemented null-moves in Mediocre. I am not exactly sure if it is bug free, or if it is optimized. What I do know is Mediocre is searching about 1-2 plies deeper in any given poisition using the same time (sometimes faster) without any noticeable decrease in tactical strength (which can be the result of cutting off lines too early).

That is just an awesome improvement! :)

As mentioned earlier null-moves is an 'unsound' pruning of the search tree, atleast in the form I am using it. It is 'unsound' because the engine only estimates some lines and decides if we should search them or not. By doing this we can sometimes miss important lines since they appear to be bad at first. But judging from the results it does not seem very unsound. :)

Here is a match between Mediocre v0.1b and Mediocre Dev (development version with null-moves). The null-moves did pretty darn well.
   Engine         Score   Results
1: Mediocre Dev 15,0/20 =011111==10110111=11
2: Mediocre v0.1b 5,0/20 =100000==01001000=00
The times used was; if the search takes more than 2 seconds, finish the depth currently on and return the result. Mediocre v0.1b could sometimes do a 4 ply search in 1.8 seconds and then take 15-20 more seconds for the 5th ply. This never occurred in Mediocre Dev, usually the last ply took about 3-4 seconds, at most 7-8.

So even though Mediocre Dev searched deeper it ended up using a lot less time total.

Keep in mind both versions are using exactly the same simple evaluation code, the only difference is the null-moves. As you can see an extra ply here and there works miracles.

Also since so many lines are cutoff I am hoping the extended evaluation I intend to write will not slow down the engine as much as it did before.

In my next post I will explain the theory of null-moves, and after some more testing I will present the new code.