[Download] #9 - Iterative Deepening

I am now finished with the iterative deepening. I have also added some piece positioning evaluations and a code that reports progress in the search to winboard.

Opening book

Notice that I am still using Yves' opening book class. Basically because I am lazy and it is working very well. It is called for in the Mediocre-class by;

book = Book.getInstance();
book.readBook();

It keeps track of still being in the opening with the useBook-boolean. To get the next move we keep track of the line so far with openingLine and get the next move with;

bookMove = book.getBestMove(openingLine);

If the move returned is "" we know we are out of the opening and set useBook to false. If the move returned is an actual move (e.g. "e2e4") we use the receiveMove-method just like if we recived a move from the opponent and play it.

Make sure you keep the 'book.zip' file as it is (zipped) and in the same directory with the same name.

That is pretty much it. As soon as I get around to it I will rewrite it and comment the code (in english and not french :).

Using the line from previous iteration

To extract best line from the previous iteration I use the sortMoves()-method in the Engine-class.

To make sure we only add the line once I have a boolean usingPreviousLine that is set to true before calling alphaBeta() and as soon as we get a new alpha value we know we reached the end of the first line and set usingPreviousLine to false.

The sortMoves()-method also sorts the captures to be searched first. We can add more sorting here as we go along.

Reporting the search progress

At any time we can use System.out.println to send a line on the form:

5 200 532 32000 e4 e5 Nf3 Nc6 Bb5

This is interpreted by winboard as a "thinking" string. The line is decoded as (what the above string means in parenthesis):

ply Current ply (ply 5)
score Evaluation in centipawns (ahead with 2.00 pawns)
time Search time in centiseconds (used 5.32 seconds)
nodes Number of nodes searched (32000)
pv Principal variation (e4 e5 Nf3 Nc6 Bb5 expected line)

The last part (pv) can be used to send any information we want, usually the principal variation is used, but we could send e.g. "Ruy Lopez" in the above line if we wanted to tell the user the opening is Ruy Lopez so far. The first four words need to be integers though, and most graphical interfaces uses these in one way or another (Arena for example calculates nodes/second from the nodes searched integer).

Mediocre sends this line after every finished call to alphaBeta(), since then we know we have a new principal variation. We could also send a new string every time the prinicpal variation changes. Or any other time we feel like reporting something.

Some positioning evaluations

I have put the evaluation in its own class called Evaluation (what else :). It is used with the static evaluate()-method that takes a Board-object and returns the evaluation. As I mentioned before I did this to be able to compare different evaluation setups.

The only real difference from before is I added piece positions evaluation to the code. They work with positioning arrays that looks like this (in the Definitions interface):

public static final int[] W_KNIGHT_POS =
{
  -10,  -5,  -5,  -5,  -5,  -5,  -5, -10, 0,0,0,0,0,0,0,0,
   -5,   0,   0,   0,   0,   0,   0,  -5, 0,0,0,0,0,0,0,0,
   -5,   0,   5,   5,   5,   5,   0,  -5, 0,0,0,0,0,0,0,0,
   -5,   0,   5,  10,  10,   5,   0,  -5, 0,0,0,0,0,0,0,0,
   -5,   3,   5,  10,  10,   5,   3,  -5, 0,0,0,0,0,0,0,0,
   -5,   5,  12,  12,  12,  12,   5,  -5, 0,0,0,0,0,0,0,0,
   -5,   4,   4,   4,   4,   4,   4,  -5, 0,0,0,0,0,0,0,0,
  -10,  -5,  -5,  -5,  -5,  -5,  -5, -10, 0,0,0,0,0,0,0,0 };

These values are added to the evaluation depending on what square the white knight is on (in this case). The board should be read both flipped and mirrored, like this:

a1,  b1,  c1,  d1,  e1,  f1,  g1,  h1, 0,0,0,0,0,0,0,0,
a2,  b2,  c2,  d2,  e2,  f2,  g2,  h2, 0,0,0,0,0,0,0,0,
a3,  b3,  c3,  d3,  e3,  f3,  g3,  h3, 0,0,0,0,0,0,0,0,
a4,  b4,  c4,  d4,  e4,  f4,  g4,  h4, 0,0,0,0,0,0,0,0,
a5,  b5,  c5,  d5,  e5,  f5,  g5,  h5, 0,0,0,0,0,0,0,0,
a6,  b6,  c6,  d6,  e6,  f6,  g6,  h6, 0,0,0,0,0,0,0,0,
a7,  b7,  c7,  d7,  e7,  f7,  g7,  h7, 0,0,0,0,0,0,0,0,
a8,  b8,  c8,  d8,  e8,  f8,  g8,  h8, 0,0,0,0,0,0,0,0

So a white knight on 'd6' is worth 12 extra points compared to a knight on 'd2'. The zeros to the right is of course the dummy board, they need to be there to get the right indexes.

I have also made arrays for pawns but these are not used yet. More arrays will be added as we go along. We should also have arrays specific for endings, so we need a way to determine when the game enters the ending.

Of course all these values are subject to change. I do not know if a white knight on 'd6' should be awarded 12 points (0.12 pawns) or 1 point, or 50 points. To get the right numbers we will have to play old versions of the evaluation against new versions and see which wins the most games. If a new evaluation wins most games, the change is an improvement.

Looking ahead

I am pretty much satisfied with the search now. I might start optimizing it a bit, especially some of the sorting and use of vectors.

One of the bigger bottlenecks is the three-fold repetition check. We need to generate a FEN-string on pretty much every move in the search, and this takes a lot of time. With Zobrist keys we can keep an updated comparable of the position in the Board-object with basically no cost at all.

But for now it is time to tweak the evaluation. As it is now there are many flaws with the way Mediocre plays, for example it does not advance pawns in the ending since it can not see the benefit of it due to the horizon effect. If we award pushing pawns forward in the ending, this will be taken care of.

mediocre(dl9)