📄 ics 180, april 1, 1997.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0049)http://www.ics.uci.edu/~eppstein/180a/970401.html -->
<HTML><HEAD><TITLE>ICS 180, April 1, 1997</TITLE>
<META content="text/html; charset=gb2312" http-equiv=Content-Type>
<META name=Owner value="eppstein">
<META name=Reply-To value="eppstein@ics.uci.edu">
<META content="MSHTML 5.00.2014.210" name=GENERATOR></HEAD>
<BODY><IMG alt="" height=72 src="ICS 180, April 1, 1997.files/icslogo2.gif"
width=472>
<P><A href="http://www.ics.uci.edu/~eppstein/180a/index.html">
<H1>ICS 180A, Spring 1997:<BR>Strategy and board game programming</H1></A>
<H2>Lecture notes for April 1, 1997<BR>A brief history of computer game
programs</H2><BR>Sources: most of the earlier stuff comes from papers in the
books "Computer Chess Compendium" and "Computer Games" (both Springer-Verlag),
consisting of reprints of many original papers including Shannon's. Some of the
recent material on Deep Blue is reworded from material on <A
href="http://www.chess.ibm.com/">IBM's web site</A>. Other sources include web
sites linked to by this page.
<P><B>1950</B>
<BLOCKQUOTE>Claude E. Shannon writes the first article on computer chess:
"Programming a computer for playing chess", Philosophical Magazine 41:256-275.
He writes "Although perhaps of no practical importance, the question is of
theoretical interest, and it is hoped that a satisfactory solution of this
problem will act as a wedge in attacking other problems of a similar nature
and of greater significance". Modern chess programs still follow the lines
laid out by Shannon.
<P>Shannon notes the theoretical existence of a perfect solution to chess and
the practical impossibility of finding it. He describes two general
strategies, both based an a heuristic "evaluation function" for guessing
whether a position is in favor of one person or the other:
<BLOCKQUOTE><I>Shannon Type A</I> - expand all sequences of possible moves
out to a fixed "horizon" (number of levels), combine the evaluations of
these sequences in a simple tree computation ("minimax"), use the combined
evaluation to choose the best move.
<P><I>Shannon Type B</I> - only perform selective expansion of certain
lines, using knowledge to prune uninteresting branches. For example,
Turing's 1951 program only expanded lines involving captures.
</P></BLOCKQUOTE>Shannon thought that type B was clearly better but debate
still continues today (you can find proponents of both sides on
rec.games.chess.computer). Shannon's evaluation combines terms for material
(P=1, N=B=3, R=5, Q=9) and positional advantages, similar to modern evaluation
functions. </BLOCKQUOTE>
<P><B>1951</B>
<BLOCKQUOTE>Alan Turing describes and hand-simulates a computer chess program
of type B. Play best described as "aimless"; loses to weak player. </BLOCKQUOTE>
<P><B>1956</B>
<BLOCKQUOTE>Type A program (for simplified 6x6 chess variant) implemented on
MANIAC-1 (11Khz, 600 words of mem) computer at Los Alamos. Does 4-ply search
in 12 min. Beats weak players. </BLOCKQUOTE>
<P><B>1957</B>
<BLOCKQUOTE>Type B program implemented on IBM 704 (42Khz, 7K words). Does full
chess 4-ply in 8 min. Passable amateur. </BLOCKQUOTE>
<P><B>1958</B>
<BLOCKQUOTE>Newell, Simon and Shaw introduce alpha-beta pruning, a general
game-search technique which effectively doubles the length of move sequences
one can examine. </BLOCKQUOTE>
<P><B>1959</B>
<BLOCKQUOTE>Arthur Samuel begins experimenting with automatic learning
techniques to improve the play of a checkers program. </BLOCKQUOTE>
<P><B>1962</B>
<BLOCKQUOTE>Alan Kotok's B.S. thesis project from M.I.T., a program called
MacHack for IBM 7090 computers, examines 1100 positions/minute. </BLOCKQUOTE>
<P><B>1967</B>
<BLOCKQUOTE>Greenblatt chess program (MacHack 6) on DEC PDP-6 (200Khz)
evaluates about 10 positions/second. It competes in 4 amateur chess
tournaments, wins 3 games, draws 3, loses 12. </BLOCKQUOTE>
<P><B>1968</B>
<BLOCKQUOTE>Zobrist writes the first Go program. It plays like a complete
beginner. </BLOCKQUOTE>
<P><B>1971</B>
<BLOCKQUOTE>The "Technology" chess program wins 10 pts out of 26 in six
tournaments. Is this the first chess program written in a high-level
prgramming language? It runs on a PDP-10 (1Mhz), and examines 120
positions/second. </BLOCKQUOTE>
<P><B>1973</B>
<BLOCKQUOTE>Until this point, most or all chess programs have been of type B.
Programmers Slate and Atkin, revising their overly complicated chess program
in preparation for the 1973 Computer Chess Championships, return to a type A
search routine. Their program Chess 4.0 wins, and other programmers start to
switch from type B to type A. On a CDC 6400 a later version (Chess 4.5)
processes from 270 to 600 positions/second. </BLOCKQUOTE>
<P><B>1975</B>
<BLOCKQUOTE><A
href="http://www.cis.uab.edu/info/faculty/hyatt/hyatt.html">Robert Hyatt</A>
begins developing Cray Blitz, for a long time the fastest program and from
1983-1989 the world computer chess champion. As of 1983 it was searching
40-50K positions/second, only a little slower than current programs on fast
pentiums. Hyatt is still very active today in computer chess with his free
program <A href="ftp://juniper.cis.uab.edu/pub/hyatt">Crafty</A>. </BLOCKQUOTE>
<P><B>1977</B>
<BLOCKQUOTE>Belle, first special-purpose chess hardware, built by Condon &
Thompson at Bell Labs.
<P>Chess 4.6 beats a grandmaster (Stean) at speed chess. </P></BLOCKQUOTE>
<P><B>1979</B>
<BLOCKQUOTE>BKG, written by Hans Berliner, beats the world backgammon champion
in a match. </BLOCKQUOTE>
<P><B>1982</B>
<BLOCKQUOTE>IAGO plays Othello at world-championship level (according to
then-human champion Jonathan Cerf) but does not actually play against
championship-level human competition. </BLOCKQUOTE>
<P><B>1988</B>
<BLOCKQUOTE>Deep Thought, predecessor of Deep Blue, created by a team of
Carnegie-Mellon U. graduate students. The basic version of Deep Thought's
chess engine contained 250 chips and two processors on a single circuit board
and was capable of analyzing 750,000 positions per second or 10 half moves
ahead. That same year Deep Thought became the first computer to defeat a
Grandmaster in a tournament (Bent Larsen, who had at one time been a contender
for world champion, being defeated by Bobby Fischer in a preliminary
championship round). </BLOCKQUOTE>
<P><B>1989</B>
<BLOCKQUOTE>An experimental six-processor version of Deep Thought, searching
more than two million positions/second, played a two-game exhibition match
against Gary Kasparov, the reigning world champion, and was beaten.
</BLOCKQUOTE>
<P><B>1992</B>
<BLOCKQUOTE><A href="http://web.cs.ualberta.ca/~chinook/">Chinook</A> checkers
program loses a match to the human world champion, Marion Tinsley, 4-2 (with
33 draws). </BLOCKQUOTE>
<P><B>1993</B>
<BLOCKQUOTE>Deep Thought defeated Judit Polgar, at the time the youngest
Grandmaster in history and still the strongest female player in the world
(ranked in the top 20 grandmasters), in another two-game exhibition match.
</BLOCKQUOTE>
<P><B>1994</B>
<BLOCKQUOTE>Tinsley forfeits match to Chinook due to illness. Chinook becomes
world checkers champion. </BLOCKQUOTE>
<P><B>1996</B>
<BLOCKQUOTE>IBM's new chess machine Deep Blue (a 32-processor parallel
computer with 256 VLSI chess engines searching 2-400M moves/second) beats
reigning world champion Gary Kasparov in the first game of a six-game match,
but loses the match. </BLOCKQUOTE>
<P><B>1997</B>
<BLOCKQUOTE>Kasparov - Deep Blue rematch to be held this quarter. </BLOCKQUOTE>
<HR>
<A href="http://www.ics.uci.edu/~eppstein/">David Eppstein, <A
href="http://www.ics.uci.edu/">Dept. Information & Computer Science</A>, <A
href="http://www.uci.edu/">UC Irvine</A>, Monday, 04-Jan-1999 14:37:05 PST.
</BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -