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.