Hossa - Internal Information

Changelog

Because Hossa is not public available, the following information is probably only interesting for myself.

1.172 (05-01-2006)

Fixed bug in undefined initialization of white squares and black squares bitboards. Amazingly simply removing this bug made Hossa playing weaker. The reason was an unbalanced bad/good bishop evaluation. I improved this evaluation but still I am not sure if it made Hossa stronger.

1.173 (05-02-2006)

Started to work on endgame bitbases.
Static stalemate detection in endgame evaluation for positions where the side to move has only a king and pawns. This is useful because stalemates are not seen in qsearch.
Bugfix in pawn race detection (occured only in extremly rare positions)
The mate attractor value now depends on the material on the board. Hossa will now try to convert endgames more quickly.
100% correct static evaluation of KQKB.

Experiments with some of my own ideas!

Besides the common techniques which are part of almost every modern chess engine I work on original ideas. Some of them are already implemented. Some are experimental and are not always active if you face Hossa at ICC:

Book Learning

My approach of book learning is much more radical like e.g. the book learning of crafty or Fritz. The source of Hossa's opening book is an arbitrary game database. When building the book I create a move tree from this database and evaluate each node with a minimax algorithm. If you only consider this step and if you would use the resulting opening book without modifications in the future, your program would play rather bad, because a single low quality game could influence the value of a large sub tree.

Now here comes the trick: after each game which Hossa plays I add this game to the book database and reevaluate the tree. This approach has at least the following advantages:

Hossa learns openings from his opponents.
Even if you have only a very small initial game database, Hossa will learn the essential openings very fast.
It doesn't matter if the game database contains also low quality games. This lines will soon be ignored because of the minimax evaluation.
The approach implements a positive and negative book learning. Positive learning: if an opponent plays a line which Hossa won before it doesn't have to compute the winning moves again, because they are already in the opening book. Negative learning: if Hossa loses with a certain line the node where the line starts will get a low value after the reevaluation, so Hossa won't play it again.
Hossa will (almost) never lose the same game twice.
Hossa will never have to compute the same move twice. This saves a lot of time.
If you run a series of games against the same opponent the result will be a killer book.
It is easy to implement.

Besides these advantages there are also some problems:

It can happen that Hossa learns that all moves of a certain side are bad. This problem occurred when I started to implement the book learning: I let Hossa play a lot of games over night against a stronger engine (I think it was phalanx) where Hossa always had white. Hossa lost almost any game and the result was, that he thought that any move for white is losing. It chooses the move, which leads to the longest losing line, but in the end it was possible for the black player - if he knew the opening book - to win each game. In practice this problem is not important if
- the opening book is reasonable large,
- where Hossa doesn't play only one side in each game and
- where it is rather likely that the opponent doesn't follow the losing book line so far that a position with a decisive disadvantage for Hossa will be reached
- It takes some time to reevaluate the modified opening book after each game, although this can be done rather efficiently because only a small part of the whole tree has to be examined.

Improved pawn endgame playing skill

Some aspects:

forward pruning for useless underpromotions.
detection of pawn chunks which don't influence the result of the game.
optimized methods for pawn endgames (move ordering, ...).
detection of deadly won positions which will become pseudo-terminal nodes.

Lucky punch mode

When Hossa has a very bad position but still has enough material to start an attack then he doesn't take care too much about losing more material but rather tries to start a wild attack against the opponent's king. This approach is especially useful in blitz games against human opponents.

Mobility

Hossa has some nice knowledge about mobility. E.g. he knows statically if a rook or a queen is trapped even in the middle of the board. These are rather expensive eval terms of course. This is a reason why Hossa is a slow searcher. In the following position you can see this feature in action:

blocked rook

1r6/1pb1k1p1/4p2p/1p1p4/3Pp2P/1R2P1PB/1P2P1K1/8 b

Hossa needs less than 2 seconds on an Athlon 900 to see 1... b4!!. Here is his analysis:

  depth  value    time    nodes pv
    1    +0.43    0.01        3 1... b8f8 2.b3xb5
   <1>   +0.43    0.01       62 1... b8f8 2.b3xb5
    2    +0.43    0.01       81 1... b8f8 2.b3xb5
   <2>   +0.43    0.02      218 1... b8f8 2.b3xb5
    3    +0.36    0.02      595 1... b8f8 2.h3g4 c7d6 3.b3xb5
   <3>   +0.36    0.03     1522 1... b8f8 2.h3g4 c7d6 3.b3xb5
    4    +0.25    0.04     2235 1... b8f8 2.b3xb5 b6 3.g2h2
   <4>   +0.25    0.06     4340 1... b8f8 2.b3xb5 b6 3.g2h2
    5    +0.37    0.08     5839 1... b8f8 2.b3xb5 b6 3.h3g4 e7f6
   <5>   +0.37    0.13     9329 1... b8f8 2.b3xb5 b6 3.h3g4 e7f6
    6    +0.23    0.17    13171 1... b8f8 2.b3xb5 b6 3.h3g4 e7f6
                                4.g2h2
  2/6    +0.29    0.25    21108 1... g5 2.h4xg5 b8g8 3.b3c3 c7a5
                                4.c3a3
   <6>   +0.29    0.35    31516 1... g5 2.h4xg5 b8g8 3.b3c3 c7a5
                                4.c3a3
    7    +0.36    0.45    43060 1... g5 2.b3xb5 g5xh4 3.g3xh4 b8g8
                                4.g2f1 g8f8 5.f1g1 b6 6.g1h1
 14/7    +0.42    0.69    71846 1... c7a5 2.b3xb5 a5d2 3.b5b3 b5
                                4.b3a3 b8f8
   <7>   +0.42    0.78    83075 1... c7a5 2.b3xb5 a5d2 3.b5b3 b5
                                4.b3a3 b8f8
    8    +0.22    0.88    95087 1... c7a5 2.b3xb5 a5d2 3.b5b3 b5
                                4.b3a3 b8f8 5.g2h2
  2/8    +0.28    1.37   147023 1... g5 2.h5 b8f8 3.b3xb5 b6
                                4.h3g4 e7f6 5.g2h2
!   8    +0.96    1.82   199080 1... b4 2.b3xb4 b5 3.h3g4 c7d6
                                4.b4b3 b4 5.g2f2
!  <8>   +0.96    1.82   199903 1... b4 2.b3xb4 b5 3.h3g4 c7d6
                                4.b4b3 b4 5.g2f2
    9    +1.11    1.99   222381 1... b4 2.b3xb4 b5 3.g4 c7d6
                                4.b4b3 b4 5.g5 h6xg5 6.h4xg5
   <9>   +1.11    2.04   230015 1... b4 2.b3xb4 b5 3.g4 c7d6
                                4.b4b3 b4 5.g5 h6xg5 6.h4xg5

Blocked position detection

Almost every program has major problems with blocked positions where one side has a big material advantage. Look at the following example:
blocked position diagram

4k3/8/1p1p4/pPpPp1p1/P1P1PpPp/5P1P/2BB4/K7 b

How can a program see that there is no way to win this position? Here is my idea: if you have a position with a big material advantage you can expect that your advantage will become even bigger after some moves. If you play some moves and you still have a big advantage but the position is not better than before then something is wrong. It's even more suspicious if the opponent doesn't have to change his position very much to keep the score. If this happens then it's very likely that we have a blocked position.

Description of standard techniques

Alpha Beta Pruning

On 09-28-98 Bruce Moreland (author of Ferret) wrote an instructive posting about alpha beta pruning at CCC. He gave me the permission to add his posting to my site.

"Search" is a recursive routine. Each call to Search is designed to return the score of the current position, given a particular search depth.

Two values are passed in to Search. These values are alpha and beta, and they represent a lower- and an upper-bound on the value of the position. Alpha is always less than beta.

To expand a node in the search, you generate all of the legal moves and try them out one by one. You recursively call Search and each of the resulting positions.

If one of these positions scores >= beta, you immedately return beta. This is called a fail-high. A fail-high happens when you find a move that is better than you will allow. If you get one, you know that the opponent has some strategy that will prevent you from achieving the position you are searching, and that they will want to do this, because the position is great from your point of view.

If one of these positions scores <= alpha, you completely ignore it. These are positions that aren't good from your point of view. You have to continue searching in order to try to find a position that is good for you. If you don't find one, you know that your opponent can force you to reach this node or a node that is equivalent or worse. Searching through every legal move, and finding no moves that result in a score that is > alpha is called a fail-low. This represents a case where you might have problems.

If a position returns a value that is > alpha and < beta, this is called a PV (principle variation) node. It represents a node that is no worse than any node that will be reached if both sides play optimally. It represents you best guess about what might happen in the position. If you find one of these, you have to continue searching moves, in case you fail high, but you can no longer fail low.

When you try a move, you recursively call Search. In order to take into account the fact that the goal of the game is different, since the other side is trying to find the best move from its point of view, the current alpha and beta bounds are swapped, and the result of Search is negated. So you get something like this:

val = -Search(-beta, -alpha);

What this also means is that if you fail low in a node, you'll return "alpha", which gets flipped around and becomes beta from the point of view of the caller of this instance of Search. So if you fail low, the instance of Search that called you will fail high. Likewise if you fail high, your caller will have to ignore this move and continue searching.

I explained how this all works, but I didn't explain what it does. What it does is eliminate positions, before all legal moves are searched from that position, if one of the moves searched from that position is found to lead to a situation that is so good that your opponent can't afford to allow you to reach it.

For instance, say that material is even, and you find one move that keeps material even. Let's say you check the next possible move, and you find that if you make that move, there is a strategy that lets your opponent win a piece. You don't need to continue seeing what else they can do to you, because losing a piece is bad enough. You know that you at least lose a piece, there is no way to avoid this, so you don't have to worry about whether they can also mate you from that position. You know that given your choice, you will always choose the position that keeps the material level, rather than the one where you lose a piece at least. If you think about this, humans do this to an extent when they play, but it is not a rigidly structured as the way a chess program does it.

bruce

Null Moves

Null Moves were described by Chrilly Donninger in the following paper:

Donninger Chr. (1993)
"Null Move and Deep Search: Selective Search Heuristics for Obtuse Chess Programs",
ICCA Journal, Vol. 16, No. 3, pp. 137-143.

Here is how Bob Hyatt describes null moves:

"Simple explanation.. if you could make two moves in a row at one place in a game, of your choice, you could be world champion with no problems. Two moves in a row is a crushing advantage. In chess... suppose you reach a position where it is your move, and your opponent says "I pass, move again". You do, but you can't do anything good. In such a case, you could rightfully say 'my position sucks'.

That is how null move goes... in the chess tree you try a null move and see if your opponent can do anything to you. If not, you 'fail high' there and say 'your position sucks, try something else.' And since the two-moves-in-a-row is such a big advantage, we can search the resulting tree to a shallower-than- normal depth which saves a lot of time..."

The following more technical explanation was given by Bruce Moreland in CCC:

You enter a node, and you're all ready to search all of the moves here to, let's say, 6 plies.

The case we are interested in is the one where you are massively winning, so you will not actually search all of the moves. You'll search the first one, and the resulting position will be awesome, so you'll quit. That's just normal alpha-beta search.

But that's still one move searched to 6 plies, just to tell you that you are winning.

What you do with the null move is assume it's the opponent's turn to move and search to some reduced depth, probably most commonly 4 plies in this case.

In the case I'm talking about, maybe the opponent can find a salvation if they get to move here, in which case you ignore the result of the null move, and search the rest of the moves normally. But perhaps they are losing, and getting to make a move doesn't help. In this case you assume that if you made a move you'd be even better, so you quit.

To try to answer your question, this search is shallower, but it's still a fairly strong search. Letting the opponent move first is usually an advantage, so the result from this search, if it lets you quit (fail high), is usually pretty accurate.

You get burned in two cases:

You are in zugzwang, meaning your position will disintegrate if you move, but it is fine if you don't. In this case, you could search 50 plies instead of 4, and you'll still think your position was dandy. So in this case the null move is terrible. You get burned because passing a move isn't legal in chess. If it was legal, this problem wouldn't happen.
There is a threat against you, which is a little too deep to see with the reduced depth search. Your opponent can rip you in 5 plies, but the 4-ply search didn't see this. If you'd done a normal 6-ply search, you get to make a move, but since the threat is unstoppable perhaps this move doesn't do any good. Now the opponent gets 5 plies in response, and that's enough to see that they can kill you. So in this case the null move overlooked an unstoppable threat, which has nothing to do with zugzwang. Unfortunately a common case involves unstoppable mates, so when this case comes up it is often a disaster.

Both of these situations come up, but in the typical case they don't outweigh the advantage of being able to go 10x faster in dumb positions, of which there are a lot.

bruce

NegaScout

NegaScout is a search algorithm similar to Alpha Beta, but more efficient. The main idea is to search with a null window in most of the nodes and only with a wider window where it is necessary. NegaScout was invented by Prof. Dr. Alexander Reinefeld. On his homepage you will find a pdf file which contains his original article about NegaScout in the ICCA Journal.

Here is the algorithm in C-like notation.

/* compute minimax value of position p */
int NegaScout(Position p, int alpha, beta, d);
{
    int a, b, t, i;

    determine successors p.succ[0],...,p.succ[w-1] of p;
    if(d==0) return Evaluate(p);    /* leaf node */

    a = alpha;
    b = beta;
    for(i=0; i<w; i++)
    {
        t = -NegaScout(p.succ[i], -b, -a, d-1);
        if((t>a) && (t<beta) && (i>0) && (d<maxdepth-1))
            a = -NegaScout(p.succ[i], -beta, -t, d-1);    /* re-search */
        a = max(a, t);
        if(a>=beta) return a;    /* cut-off */
        b = a+1;    /* set new null window */
    }
    return a;
}