Because Hossa is not public available, the following information is probably only interesting for myself.
1.172 (05-01-2006)
1.173 (05-02-2006)
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:
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:Besides these advantages there are also some problems:
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.
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:
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
Almost every program has major problems with blocked positions where one side has a
big material advantage. Look at the following example:
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.
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.
bruceNull 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:
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.
bruceNegaScout 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; } |