📄 g13gam -- game theory -- computer chess notes.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0059)http://www.maths.nott.ac.uk/personal/anw/G13GT1/compch.html -->
<HTML><HEAD><TITLE>G13GAM -- Game Theory -- computer chess notes</TITLE>
<META content="text/html; charset=big5" http-equiv=Content-Type>
<META content="MSHTML 5.00.2614.3500" name=GENERATOR></HEAD>
<BODY bgColor=#d8a070 text=black>
<H1>G13GAM -- Game Theory </H1><A name=top></A>
<H2>Further notes on computer chess </H2>Most of these topics are not
`examinable'; they are here mainly for interest, especially for those of you who
may find yourselves writing programs for some game or other. I have tried to
keep the discussion general as far as possible, but a little of it is very
chess-specific.
<P>
<UL>
<LI>Basic search strategy, including code, was discussed in lectures and real
live code given on a handout obtainable from me.
<LI><A
href="http://www.maths.nott.ac.uk/personal/anw/G13GT1/alphabet.html">Alpha-beta
pruning</A> is discussed on a separate page.
<LI><A
href="http://www.maths.nott.ac.uk/personal/anw/G13GT1/compch.html#code">Complete
source code listings of some programs</A>. See me if you want/need further
references to chess-related Web pages.
<LI><A
href="http://www.maths.nott.ac.uk/personal/anw/G13GT1/compch.html#deep">Iterative
deepening</A>.
<LI><A
href="http://www.maths.nott.ac.uk/personal/anw/G13GT1/compch.html#kill">Killers
and history</A>.
<LI><A
href="http://www.maths.nott.ac.uk/personal/anw/G13GT1/compch.html#tt">Transposition
tables</A>.
<LI><A
href="http://www.maths.nott.ac.uk/personal/anw/G13GT1/compch.html#quies">Quiescence</A>.
<LI><A
href="http://www.maths.nott.ac.uk/personal/anw/G13GT1/compch.html#ext">Extensions</A>.
<LI><A
href="http://www.maths.nott.ac.uk/personal/anw/G13GT1/compch.html#horiz">The
horizon effect</A>.
<LI><A
href="http://www.maths.nott.ac.uk/personal/anw/G13GT1/compch.html#null">Null
moves</A>.
<LI><A
href="http://www.maths.nott.ac.uk/personal/anw/G13GT1/compch.html#remot">Remoteness</A>.
<LI><A
href="http://www.maths.nott.ac.uk/personal/anw/G13GT1/compch.html#psych">Psychological
considerations</A>.
<LI><A
href="http://www.maths.nott.ac.uk/personal/anw/G13GT1/compch.html#hard">Hardware
and software considerations</A>.
<LI><A
href="http://www.maths.nott.ac.uk/personal/anw/G13GT1/compch.html#prob">Problems</A>.
<LI><A
href="http://www.maths.nott.ac.uk/personal/anw/G13GT1/compch.html#end">Endgame
databases</A>.
<LI><A
href="http://www.maths.nott.ac.uk/personal/anw/G13GT1/compch.html#open">Openings</A>.
</LI></UL>
<P><A name=code>
<H3>Source code for a complete program </H3>For anyone who wants to look at
real, live, code for a chess-playing program, feel free to explore the directory
<A href="ftp:Notchess"><I>/maths/staff/anw/chess/Notchess</I></A> on the
Departmental computers. The version there is not quite my latest, but it'll do!
This program 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 <I>Notchess</I> 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!
<P>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 <A
href="ftp://ftp.cis.uab.edu/pub/hyatt">Bob's FTP directory</A>; 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 <A href="ftp://src.doc.ic.ac.uk/gnu">Gnu</A> directory of the Imperial
College archive -- look for the latest version of <I>gnuchess</I>. A useful
resource in this connexion is <A
href="http://www.research.digital.com/SRC/personal/Tim_Mann/chess.html">Tim
Mann's chess page</A>, which gives an authoritative overview of the Gnuchess
program, and especially the best way to interface Gnuchess and Crafty with
windowing systems [<I>e.g.</I> for the PC!], from one of the authors.
<P>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, <A href="http://www.xs4all.nl/~rebchess/edsoft.htm">Rebel Decade</A>
plays quite well enough for most opposition. Another usable demo is that for <A
href="http://www.chemeng.ed.ac.uk/people/steve/cbdemo.html">ChessBase</A>, based
on the Fritz program. The <A
href="http://www.gambitsoft.com/gambit1e.htm">Gambit-Soft home page</A> 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!
<P><A name=deep>
<H3>Iterative deepening </H3>... 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.
<P>The outcomes of the shallower searches will be held in the <A
href="http://www.maths.nott.ac.uk/personal/anw/G13GT1/compch.html#tt">transposition
table</A>, 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.
<P>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 <A
href="http://www.maths.nott.ac.uk/personal/anw/G13GT1/compch.html#quies">quiescence</A>
and <A
href="http://www.maths.nott.ac.uk/personal/anw/G13GT1/compch.html#ext">extension</A>.
<P><A name=kill></A>
<H3>Killers and history </H3>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.
<P><A name=tt></A>
<H3>Transposition tables </H3>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.
<P>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 <I>2k</I> deep in the tree can be reached
in <I>(k!)<SUP>2</SUP></I> 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.
<P>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 <A
href="http://www.maths.nott.ac.uk/personal/anw/G13GT1/deep">iterative
deepening</A>. 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.
<P>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.
<P><A name=quies></A>
<H3>Quiescence </H3>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 ...
<P><A name=ext></A>
<H3>Extensions </H3>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'.
<P><A name=fhr></A>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
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -