g13gam -- game theory -- computer chess notes.htm

这是博弈论算法全集第八部分:综合论述,其它算法将陆续推出.以便与大家共享

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 <I>static</I> evaluation at the current node returns a 
value which would cause a cutoff. 
<P>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. 
<P><A name=horiz></A>
<H3>The horizon effect </H3>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]. 
<P>The problem is becoming less acute partly because of <A 
href="http://www.maths.nott.ac.uk/personal/anw/G13GT1/compch.html#ext">sex</A>, 
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. 
<P><A name=null></A>
<H3>Null moves </H3>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 <I>zugzwang</I> 
[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 <A 
href="http://www.maths.nott.ac.uk/personal/anw/G13GT1/compch.html#fhr">fail-high 
reductions</A>, to control which parts of the tree are searched less thoroughly. 

<P><A name=remot></A>
<H3>Remoteness </H3>In Othello, where moves cannot be `undone' and the game 
marches inexorably to its conclusion, moving towards good positions is enough to 
win; but in Chess, it is not enough to have a won position, you must actually 
win it. This leads to a curious phenomenon -- less common now than it used to 
be, thanks to increased search depths and selectivity, and thanks to an 
awareness of the problem. The simplest example in Chess can occur in the ending 
King and Queen against lone King. This is a very easy win for the player with 
the Queen; but suppose that the actual mate is too deep [it is often five or six 
moves away] for the program to see. Then it knows it is winning [it is a queen 
up], and it is liable to play the first [essentially random] move that comes 
into its head that maintains that advantage, never making progress towards 
actually winning. An even starker form can occur if it <I>does</I> see the mate; 
the program may see, say, a mate in 2, say `Aha, here is a forced quick win, 
I'll play that', and overlook, by beta cutoff, a mate in 1. That's OK, unless on 
the next move, and the next move, and the next move, ..., it continues to do the 
same thing. Very embarrassing! Many programs these days switch into a 
mate-in-<I>n</I> mode once they have found the win, where <I>n</I> is reduced 
after every move, and moves that don't implement the mate in <I>n</I> are 
ignored. 
<P><A name=psych></A>
<H3>Psychological considerations </H3>Playing a game of perfect information 
<I>ought</I> to be just a matter of playing the best move, but it isn't, and 
there are lots of other things that a program has to do. Here are a few: 
<P><I>Draws and `contempt'</I>: 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! 
<P><I>Complication vs. simplicity</I>: 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'. 
<P><I>Time management</I>: 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 <I>(a)</I> deciding 
whether to embark on the next depth or to stop here and play the best move found 
so far; and <I>(b)</I> 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 <I>(b)</I>. 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 <I>need</I> 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. 

<P><A name=hard></A>
<H3>Hardware and software considerations </H3>There are zillions of possible 
topics here, including special-purpose chess [or other] hardware, the impact of 
parallel processing in multi-processor or networked machines, bit-boards, 
efficient move generation, search <I>vs.</I> evaluation, <I>etc., etc,</I>. Life 
is too short -- see me if any of these things interest you. 
<P><A name=prob></A>
<H3>Problems </H3>Chess <I>problems</I> ["White to play and mate in 3", or 
whatever] are different from <I>games</I>, where you don't really care how many 
moves it takes to win. You can turn a program into a mate-finder simply by 
zeroing the evaluation function [so that only actually mating produces a 
non-zero result]; but problemists are also concerned with artistic properties of 
the solution, which are hard to assess from a materialistic program. Some chess 
problems have different conditions: for example, `helpmates' are problems in 
which White and Black co-operate in trying to construct a mating position, from 
a starting position in which any such outcome seems very unlikely. Helpmates 
cannot be solved by ordinary programs, nor can they be solved `merely' by 
telling Black to `play badly' [which interferes with pruning]. 
<P><A name=end></A>
<H3>Endgame databases </H3>In the final stages of a game of chess, there are 
often very few pieces on the board, and the number of configurations is small 
enough to allow exhaustive analysis and the construction of databases of the 
outcomes. For example, when five pieces remain [<I>e.g.</I> king and queen 
<I>vs.</I> king, rook and knight], there are fewer than 160 million 
configurations [allowing for symmetries], which is within the scope of a 
reasonably powerful computer. 
<P>Such analysis has thrown up a number of surprises over the years. The first 
was when king and queen <I>vs.</I> 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 <I>vs.</I> 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. 
<P>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. 
<P><A name=open></A>
<H3>Openings </H3>The opening phases of Chess, Go, Othello, Draughts and so on 
suffer from the opposite phenomenon. Here there is no certainty, but thousands 
of strong players have been studying the initial position and have written about 
or played their findings. We don't want our programs to waste their time 
re-discovering these moves, so there is usually a database of `approved' opening 
lines which the computer will play more-or-less instantly. 
<P>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. 
<P><A name=tail></A><A 
href="http://www.maths.nott.ac.uk/personal/anw/G13GT1/compch.html#top">top of 
page </A>
<HR>
<A href="mailto:[e-mail]"><IMG alt=border=0 
src="G13GAM -- Game Theory -- computer chess notes.files/mailme.gif"> E-mail 
me</A>. <A href="http://www.maths.nottingham.ac.uk/personal/anw"><IMG 
alt=border=0 
src="G13GAM -- Game Theory -- computer chess notes.files/home-btn-s.gif"> My 
home page</A>. <A href="http://www.nottingham.ac.uk/"><IMG alt=border=0 
src="G13GAM -- Game Theory -- computer chess notes.files/logo.gif"> The 
University of Nottingham</A>. 
<HR>
Copyright &copy; Dr A. N. Walker, 1997. <BR>This Web page may be freely used for 
purposes related to the above module or for private study; requests for 
permission to make other uses should be referred to the author. </BODY></HTML>