Source code for a complete program
If you are a member of this School, then you can look at
real, live, code for a chess-playing program in the
directory /maths/staff/anw/chess/Notchess
on the School's computers.
Otherwise, you may be able to explore an
equivalent directory using anonymous ftp.
The version there is not my current version, and in particular the
static evaluation is very limited.
You should be warned that Notchess was written some years ago,
and the old version you have access to has not been developed
since then;
there are much better freebie programs around now, especially if
you want a seriously strong opponent.
Notchess was originally written as a sort-of demo program for this module, but it was overtaken by events and a request to enter it in a tournament. Unsurprisingly, since it was only debugged a couple of days before the start, and it had been intended for clarity rather than speed, it came last. The following year, I again received a request to enter Notchess for the so-called `Uniform Platform' competition, and it won one game and drew a couple, so at least avoided the wooden spoon. However, in the attempt to make it usable for the tournament, clarity suffered, and it is not a program I would commend for style. Some day, I'll get around to re-writing it twice, once for this module and once in an attempt to play well!
Two much stronger programs which you can retrieve [free!] if you like from the Net are Crafty and Gnuchess. Crafty is an ongoing project by Bob Hyatt. You can retrieve source and/or executables from Bob's FTP directory; don't download the `large book' unless you know exactly what you're doing! Bob has been a leading expert in the field for many years, and his program is extremely strong. Gnuchess started as a collaborative effort on the Net to write a sort-of joint program, loosely tied in with the Gnu [`Gnu's Not Unix'] project of freely available high-quality software. For some years now it has seen little active development, but it remains a fairly strong program. You can retrieve source from the Gnu directory of the Imperial College archive -- look for the latest version of gnuchess. A useful resource in this connexion is Tim Mann's chess page, which gives an authoritative overview of the Gnuchess program, and especially the best way to interface Gnuchess and Crafty with windowing systems [e.g. for the PC!], from one of the authors.
If you do not want source, merely the executables for a PC, then several of the commercial chess programs are [legitimately!] available in demo form. For example, Rebel Decade plays quite well enough for most opposition. Another usable demo is that for ChessBase, based on the Fritz program. The Gambit-Soft home page also contains many pointers to freeware, shareware and other information. I've found Gromit to be a good opponent, others speak highly of Arasan [both freely available from Gambit-Soft]. There are also lots of programs out there that you can pay for!
The outcomes of the shallower searches will be held in the
transposition table, so there is no significant penalty
associated with repeated searches.
For example, if you have searched the current position to depth (say) 10,
then after you have moved and your opponent has replied, you should still
have the outcome of the search of the resulting position to depth 8 in
the table, so that the searches to depths 1, 2, ..., 8 are instantaneous,
and you can effectively start with the search to depth 9.
There is no theoretical guarantee that deeper searches are any better
than shallow ones, though common sense suggests that they should be.
In real life, each extra "ply" [move] usually gives a significant
but not decisive advantage;
three or more extra plies essentially guarantee a win against a program
with a similar static evaluation function.
The notion of "depth of search" is complicated by the concepts of
quiescence and extension.
This is particularly useful in games like chess and go where transpositions
[reaching the identical position by two or more different routes] are likely.
In such games, two moves by the same player are quite likely to `commute';
you can play them in either order to reach the same position.
Even if they don't, you can often play a piece from one square to another
over two or three moves, and get to the same square in several different
ways.
If moves always commute [as in noughts and crosses], then a position
2k deep in the tree can be reached in (k!)2 ways,
so a TT could, in ideal circumstances, speed up the search by this factor
by enabling you to search the position once and later simply look up
its value.
The real gain is not usually so great, especially as critical lines
are typically more interlocked than random lines.
Even in games like othello where transpositions are less likely, the TT can
still be useful in its other role as repository of information.
If you record the estimated value, the depth to which this position has
been searched, and whether the recorded value is true, or a lower bound
[because of a beta cutoff] or an upper bound [an alpha fail], then this can
still help you with iterative deepening.
Another use is that when minimal windowing fails, you have to re-search
the same node;
some of the information may now be useless because the alpha-beta bounds
have changed, but some may still be valid, so that the re-search can be
much faster than the original search.
Implementation is typically via a hash function [a mapping from positions
to integers suitable for use as array subscripts];
this function [more details of which are beyond the scope of this module]
is not bijective, so collisions will occur [when quite different positions
map to the same subscript]. especially as the table fills up [which it
soon will -- for example 10K positions per second at 10 bytes stored per
position will fill a megabyte every 10 seconds].
So we need a replacement strategy to decide what to do at a collision.
This is an on-going research topic.
Keeping old values, from near the top of the tree, can save much more time
than keeping new values, from near the bottom, but the newer ones are more
likely to be needed in the immediate future.
An inverse idea is to search less deeply after a mistake.
Mistakes are determined by the fact that they allow beta cutoffs,
or `fail high', at the next depth.
So `fail high reductions' are used to reduce the depth of search
when beta cutoffs are found, thereby allowing time for a deeper search
elsewhere.
However, this wouldn't save time if you used the full search to full
depth to determine the cutoff, so an approximation is used, whereby
the depth of search is reduced if a static evaluation at the
current node returns a value which would cause a cutoff.
Yet another idea is to extend by using `conspiracy numbers'.
The conspiracy number of a node is the number of subnodes whose value
would have to change to upset the current evaluation.
Crudely, the idea is that if there are lots of ways in which you seem to
be winning, then if some of them are wrong you have a good chance that
one of them will still work, whereas if there is just one line that seems
to work, you are in trouble if it goes wrong.
So you should concentrate your efforts on the nodes with the smallest
conspiracy numbers at high levels.
The problem is becoming less acute partly because of sex,
which often extends past the delaying tactics, partly because with faster
machines the horizon is further away, and partly because a deep search
can sometimes be amazingly adept at discovering ways in which the delaying
tactics turn out actually to disrupt the pattern and allow an escape.
In fact, the fastest programs sometimes fall victim to an inverse problem:
they see that in an immensely complicated way they are going to lose
something, and to avoid it they play a very simple apparently poor move
which loses slightly less.
A famous example was a case where the computer suddenly gave away a rook
for absolutely no reason that the assembled grandmasters could see;
after the game, they set the position back and made the computer play the
`obviously' better move, and were surprised when the computer pointed
out a beautiful forced mate.
Giving up the rook lost anyway, so the better play, certainly against
humans, would have been to keep the rook and hope that the opponent
didn't see the mate.
Iterative deepening
... is the process whereby certainly at the root but possibly at all other
nodes as well a search to a given depth is guided by the outcome of a
search to shallower depth, which in turn is guided by ....
This may sound horrendously inefficient, but the amount of work to be done
grows exponentially with depth, so the sum of all the shallower searches
is small compared with one deep search, and it pays off even if only
minor improvements to move-ordering happen as a consequence.
The other main advantage of iterative deepening is that if you have to
move within a certain time limit, then deeper and deeper searches are
the simplest way to make good use of the available time.
Killers and history
Killers are moves that `kill' the opponent.
Inside a program, the simplest way of detecting this is that they
usually cause a beta cutoff.
There are lots of related things that you can do to get killers
considered early.
The most obvious is to try first moves that are likely to be killers:
in chess terms, these are captures, especially of `big' pieces by
`little' ones, checks, promotions, but most games have moves that are
more likely than others to be good.
If you find such a move, try it early!
The next, the `killer heuristic', is to keep track of recent killers,
and try them again if you find them in the move list, on the grounds that
a move that works once against random play by the opponent is quite likely
to work again.
The next extension of this idea is the `history heuristic', which is to
keep track of all killers [needs more storage], and sort moves by how
often they have turned out to be good.
You will probably want to `forget' this list from time to time, else
you will still be trying to play a move that was good dozens of moves
earlier in a position where it is no longer appropriate.
Transposition tables
A transposition table is simply an array of information about
recently-visited positions in the game.
Whenever you search a node in the game tree, you start by looking to see
whether the corresponding position is already in the TT, and, if so, whether
the information held there is useful.
Quiescence
This can be a major problem for programs.
Let us take chess as an example, though the same problem arises in
most games.
We should do static evaluations only in `quiet' positions;
it's silly to report that you have a slight advantage because your opponent
has some weak squares or a piece slightly out of play if next move he is
going to take your queen for nothing.
But how do you know he can take your queen?
Only by looking at his available moves!
But you can't do that at the bottom of the tree, which is when you want
to use static evaluation, as it amounts to looking another move deeper.
Most programs get around this by having two phases in their
dynamic search:
in phase one, all moves are searched;
in phase two, only `interesting' moves are allowed.
The degree of interest is a matter of judgement;
if you allow too much to be of interest then the interesting moves
never run out and the search goes on too long, if too little then you
miss interesting consequences.
Usually it is phase one that determines the depth of search as reported
by a program;
when it says it's on depth 5, it means that it is searching all lines that
start with no more than 5 boring moves, but it may be looking at some lines
that go on for 10, 15, 20 actual moves.
Some programs can spot amazingly deep tactical ideas with remarkably
little searching by this method, but they will then tend to miss ideas
that include lots of apparently boring moves.
Related to, but different from ...
Extensions
Simply searching everything to a given depth means that you spend too much
time looking at really stupid lines, and therefore not enough looking at
important ones.
So we would like to stop our dynamic search at shallower depths in
stupid lines and at greater depths in important ones.
To some extent, the important lines are those that include lots of
interesting moves, so the quiescence search above is one form of
`selective extension'.
Another form is `singular extension';
if you find a position where one move is found to be much better than
all the others, this move may be worth searching deeper.
Both these forms can be called `sex' -- as in `in quiescence, we only
look at sexy moves'.
The horizon effect
This was a major problem with early programs.
It is most easily explained with reference to chess.
Suppose you have a piece trapped somewhere and about to be captured --
could be anything from a pawn that can't be defended to an unstoppable mate.
The human player sees the pattern, notes that something bad is happening,
and will [if the pattern is seen in time] try to avoid it by playing
something different a few moves earlier.
The computer will often not.
Why not?
Well, there are often some delaying moves:
a harmless check, a useless attack on the opponent's queen, anything that
delays the execution of the threat.
These delaying tactics move the ill effects of the pattern further down
the tree, until they drop `over the horizon' by being too deep for the
dynamical search to see.
The human sees the pattern as being unaffected by the delaying tactics;
the computer simply sees that nothing bad happens within depth 12 [say].
Null moves
A null move is a `pass'.
In games [such as Go] where `pass' is a legal move, it must be taken into
account in the usual way;
in `cold' games, such as Othello, where it is not allowed if you have a
legal move, null moves are irrelevant;
but in Chess, an often-used tweak is to try a null move first, often with
a reduced depth.
If this fails high, then the implication is that your position is so good
that even if the other side is allowed two moves in succession it doesn't
help, and therefore that this position is not worth further search.
As such positions are very common after random moves, this brings
huge benefits in speeding up the search;
but there is a down side, in that Chess is not always hot, and there are
many so-called zugzwang [German for `move-bound'] positions where
the ability to pass would be very advantageous.
In zugzwang positions, this `null-move heuristic' is therefore very
dangerous, in that it causes you to treat as very good positions
where in fact the inability to pass makes them very bad.
The computer-chess community is split over this.
Most programs use null moves, but switch them off when the number of pieces
on the board becomes small [and zugzwang is more likely];
but there is a trend towards using other devices, such as
fail-high reductions, to control which parts of the tree
are searched less thoroughly.
Draws and `contempt': Suppose my opponent offers me a draw, or suppose that I have a manoeuvre which I can choose to play [or not] which forces a draw. What should I do? It depends not just on the situation on the board, but also on the ability of the opponent and on the state of the match or tournament. If my opponent is a grandmaster, or if my team only needs a draw from me to win the match, I might take a draw even from a technically won position; if he is a beginner, or if my team needs a win, I might refuse it even if the alternative is losing. In programs, this is usually handled by a `contempt' factor: for example, if my contempt for my opponent is two pawns, then I would refuse a draw unless losing by at least two pawns. Against Kasparov, my contempt might be a negative rook or more!
Complication vs. simplicity: If you are losing, then sometimes the best plan is to battle on and on playing `correct' moves in the hope that your opponent will make a mistake. But sometimes it is to seek complications, making objectively inferior moves that nevertheless make it more likely that the opponent will blunder. Conversely, when winning, quite often the best plan is to `sacrifice' some of your advantage in order to simplify the position and prevent your opponent from having swindling chances. Computers find this concept very difficult! An occasional manifestation of this in chess programs occurs when, for no apparent reason, the program throws away a rook, say, into a totally lost position; when you analyse to find why it did this, you discover that if it had played the `correct' move, there was a horrendously obscure plan that you had completely missed that would have won even more than a rook if you had seen it. Programs need to learn when `I hope you miss it' is more productive than `Oh dear, I'm obviously losing'.
Time management: Serious competitive games are usually played with time limits that require each player to play so-many moves in so-much time. In a program that uses iterative deepening, this amounts to (a) deciding whether to embark on the next depth or to stop here and play the best move found so far; and (b) keeping an eye on the time taken so that if the current depth turns out to be more time-consuming than expected, you can abort. Most programs try to use their time more-or-less evenly, which is why chess programs will often take their full three minutes [or whatever] even over trivially obvious moves, and they will try to use experience of other moves and other depths to judge whether the next depth will fit into the available time. The real complication comes under (b). You usually take much more time than expected if the previous `principal variation' [the line you would have played] turns out to be bad on deeper investigation. This greatly reduces the amount of pruning you get, not only in the PV but throughout the tree. In such cases, you perhaps need to spend extra time, but not so much as to have too little time for the rest of the game; and if you abort early, then you may now know that the PV is bad, but not yet have looked at any other move to see if it's any better. Some programs cope with time mnagement much better than others. A special case is Othello, where there is a `break point' after which [slow] static evaluation can be completely abandoned in favour of exhaustive analysis of the last few moves; determining this point accurately can easily be decisive.
Such analysis has thrown up a number of surprises over the years. The first was when king and queen vs. king and rook was analysed. This ending had been long `known' to be an easy win for the player with the queen, so that the player with the rook usually gave up at this point. But the computer showed that the win was in fact very difficult; a computer can usually draw against anyone who has not made a special study of this ending. The next was over king and two bishops vs. king and knight. This ending had been long `known' to be an easy draw; but the computer showed that this was usually a win for the bishops, though so difficult that no human can currently claim to understand the win [which looks like a series of random moves by the winning side, which just happen, after many moves, to lead to a position where the knight gets trapped]. Another was that the few six-piece endings [on the verge of technical possibility!] which have been analysed show ever-increasing length [hundreds of moves] before `conversion' [that is, one side or the other capturing a piece into a simpler ending] in the hardest cases; the expectation was that with more pieces, it would only take a few moves to manoeuvre into a position where simplification could be forced.
The use of endgame databases has some bizarre consequences at times. One phenomenon is where one side is easily winning -- say, by more than a queen -- and suddenly, instead of playing `strong' moves starts trying to give up the queen, in order to `convert' from a good but uncertain position into one where the absolute best play can be read off from the database. Equally bizarrely, the `losing' side may just as resolutely refuse the gifts in order to avoid the conversion.
As usual, this approach raises as many problems as it solves. One problem is `sympathy'; Kasparov may play some line with the idea of getting his pieces onto certain squares and following with some particular plan -- but the computer isn't told the plan, only the moves, and on `leaving book' may be `out of sorts' with the position, and spend several moves getting its pieces back onto squares it finds more congenial. Another is the `killer book': if your opponent is a computer whose program or opening book you know, then you can prepare opening traps specifically for that opponent. Such a trap may be a completely bogus move from the human point of view, but may reflect a discovered bug in the program or book. What is more, against a human, such a trap might work once; against a computer, the same trap works again, and again, and again, and again, unless the program is, exceptionally, one which `learns' from its mistakes. The world championships have sometimes been less about whose program plays the best chess than about whose opening book contains the best-prepared killer lines.