ArticlesOnGnuGo: GnuGoArticles.html

File GnuGoArticles.html, 14.6 kB (added by djhbrown, 20 months ago)
Line 
1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
2<HTML>
3<HEAD>
4        <META HTTP-EQUIV="CONTENT-TYPE" CONTENT="text/html; charset=windows-1252">
5        <TITLE></TITLE>
6        <META NAME="GENERATOR" CONTENT="OpenOffice.org 2.2  (Win32)">
7        <META NAME="CREATED" CONTENT="20070520;23573748">
8        <META NAME="CHANGED" CONTENT="20070521;170941">
9        <STYLE TYPE="text/css">
10        <!--
11                @page { size: 8.5in 11in; margin: 0.79in }
12                P { margin-bottom: 0.08in }
13                H2 { margin-bottom: 0.08in }
14        -->
15        </STYLE>
16</HEAD>
17<BODY LANG="en-US" DIR="LTR">
18<P ALIGN=CENTER><STRONG>Community-authored articles on Gnu Go for
19publication elsewhere</STRONG> 
20</P>
21<P>Your contributions welcomed. Please just edit the text and add
22your name to the alphabetically ordered list of authors. Or email me
23djhbrown@gmail.com something or point me to somewhere and i will work
24it in if i can.
25</P>
26<P><BR><BR>
27</P>
28<P><FONT SIZE=4><B>Worms, Dragons and Owls: How GNU Go Works </B></FONT>
29</P>
30<P><BR><BR>
31</P>
32<P>DJH Brown, nando8888,
33</P>
34<P><BR><BR>
35</P>
36<P>Not so long ago, chess was generally regarded as the intellectual
37challenge <I>par excellence</I>, but in the last 10 years, things
38have changed. Murray Campbell, the father of Deep Blue, the computer
39that defeated Gary Kasparov in 1997, recently remarked in an
40interview with the online magazine &quot;Wired&quot;: &quot;It's
41almost the end of the story for chess in the sense that matches
42between chess machines and grand masters are becoming less
43interesting because it's so difficult for the human grand masters to
44compete successfully....The current world champion, Vladimir Kramnik
45from Russia, lost a match to a PC program in November, 4-2&quot; 
46</P>
47<P>Chess programs use a basic technique which operates as follows:
48</P>
49<OL>
50        <LI><P>Some way of figuring out what is going on in a position is
51        used to
52        </P>
53        <P>(a) make an assessment of which player is winning and by how
54        much, and<BR>(b) decide which moves might favour the player whose
55        turn it is.
56        </P>
57        <LI><P>A &quot;lookahead&quot; algorithm is used to imagine
58        sequences of moves following on from each considered alternative
59        move. The imagined most likely ultimate state of play - as adjudged
60        at the end of each imagined sequence by the position evaluator
61        mentioned in 1(a) and considering all imagined follow-up sequences -
62        is regarded as the expected outcome of that alternative move, and
63        hence its utility to the player.</P>
64        <LI><P>The best (ie highest ranked) alternative move is chosen.
65        </P>
66</OL>
67<P>As there are several alternative moves at each step in the
68lookahead, the different lines together create what computer
69programmers call a &quot;search tree&quot; (because if you drew it
70out on a piece of paper, starting at the top of the page and writing
71down the alternative moves underneath, and underneath that their
72responses, and so on, it would look like an upside-down tree). The
73imagined most likely ultimate state of play deriving from each
74alternative is calculated by the heuristic assumption that the
75opponent is using the same kind of mechanism, and will choose his
76(her) most favourable move at each stage.
77</P>
78<P>There are various techniques the lookahead algorithm can employ to
79make its search efficient, but there is a fundamental problem: the
80size of the lookahead tree is an exponential function of the number
81of alternative moves at each step. At each turn, there are on average
82around 20 possible moves in chess and around 200 in Go. So to look
83ahead 7 steps, a brute force chess program would need to consider 20<SUP>7</SUP>
84= 2<SUP>7</SUP> x 10<SUP>7</SUP> = 128 x 10<SUP>7</SUP> = about 10<SUP>9</SUP>
85positions - rather a lot, but not beyond the capability of modern
86computer chips, which can perform an arithmetic calculation in as
87little as 10<SUP>-9</SUP> seconds.
88</P>
89<P>However, although the Go board is only 6 times as big as a chess
90board, the Go tree is rather more than 6 times the size of the chess
91tree.... at each step in a lookahead, there are 10 times as many
92choices. With 7 steps, there are 10<SUP>7</SUP> = 10,000,000 times as
93many things to look at. So it would take the same computer 10,000,000
94times as long to make a move in a Go game as it would to make a move
95in a chess game!
96</P>
97<P>This makes programming a computer to play Go a fascinating
98challenge. A lengthy description of some (but not all!) Go
99programming difficulties can be read at
100<A HREF="http://en.wikipedia.org/wiki/Computer_Go">http://en.wikipedia.org/wiki/Computer_Go</A>.
101One thing is for sure: the technique used by chess programs simply
102cannot work effectively for Go.
103</P>
104<P>GNU Go is an open collective effort by members of GNU, a nonprofit
105organisation that creates software for Unix-based computers. Its
106official documentation can be read at
107<A HREF="http://www.gnu.org/software/gnugo/gnugo.html">http://www.gnu.org/software/gnugo/gnugo.html</A>
108Whereas it is probably true that a camel is a horse designed by a
109committee, GNU software is not as bovine as a gnu. Rather, it is as
110smart as an Internet &quot;wiki&quot;, which represents the
111consolidated collective knowledge of many sorcerers put together
112asynchronously over a long period of time. Many GNU Go &quot;robots&quot;
113are signed up on Internet Go servers for people to play against; they
114are ranked at around 5k. Gnu Go was runner-up to KCC in the 2006
115World Computer Go Championship; tournament information can be viewed
116at <A HREF="http://computer-go.softopia.or.jp/gifu2006/English/">http://computer-go.softopia.or.jp/gifu2006/English/</A>
117</P>
118<P>......introduce worms etc GNU Go uses a variety of techniques to
119select and read out moves associated with locally tactical objectives
120such as captures, life &amp; death of groups, and connections. It
121makes a rough estimate of the balance of territory at the end of each
122lookahead sequence which is used as the means of ranking
123alternatives.
124</P>
125<P>more to come
126</P>
127<H2><A HREF="http://trac.gnugo.org/gnugo/wiki/ArticlesOnGnuGo#a2">------------------------------------------------------</A></H2>
128<P><FONT SIZE=4 STYLE="font-size: 16pt"><B>Playing for Keeps </B></FONT>
129</P>
130<P><BR><BR>
131</P>
132<P>DJH Brown,
133</P>
134<P><BR><BR>
135</P>
136<P STYLE="border: none; padding: 0in"><SPAN ID="Frame1" DIR="LTR" STYLE="float: left; width: 1.51in; height: 2.36in; border: none; padding: 0in; background: #ffffff">
137        <P ALIGN=CENTER STYLE="margin-top: 0.08in"><IMG SRC="GnuGoArticles_html_72cff812.jpg" NAME="graphics1" ALIGN=LEFT WIDTH=100% BORDER=0><BR CLEAR=LEFT><FONT SIZE=2 STYLE="font-size: 10pt"><I><BR>Jeremy
138        Bentham <BR>-  seeker of happiness</I></FONT></P>
139</SPAN>Once upon a time - in 1789 - the philosopher Jeremy Bentham
140pondered on how he could capture the concept of happiness. He
141conceived of the notion of calculating the degree to which taking a
142certain course of action would meet one's needs. His formula and its
143underlying principle became known as &quot;Utility Theory&quot; and
144was later expanded into into an ethic of utilitarianism promulgated
145by John Stuart Mill.
146</P>
147<P>And once upon another time, shortly before World War I, the
148Prussian army achieved remarkable military successes against larger
149forces due to its use of simulated war scenarios to &quot;tank-test&quot;
150alternative battlefield tactics. This fostered interest in what came
151to be known as &quot;Operations Research&quot;, which has been
152nurtured by (and possibly even partly responsible for) every major
153international conflict - including so-called free market competition
154- ever since.
155</P>
156<P>Given their very different origins and purposes, Utility Theory
157and Operations Research may seem strange bedfellows, and yet, they
158are ideal partners. Operations Research concerns itself with methods
159of identifying an optimal outcome, and Utility Theory provides a
160mechanism for measuring outcomes.
161</P>
162<P><SPAN ID="Frame2" DIR="LTR" STYLE="float: left; width: 2.62in; height: 1.96in; border: none; padding: 0in; background: #ffffff">
163        <P ALIGN=CENTER STYLE="margin-top: 0.08in"><IMG SRC="GnuGoArticles_html_m7aa55907.png" NAME="graphics2" ALIGN=LEFT WIDTH=100% BORDER=0><BR CLEAR=LEFT><FONT SIZE=2 STYLE="font-size: 10pt"><I><BR>Moore's
164        Observation</I></FONT></P>
165</SPAN><BR><BR>
166</P>
167<P>Board games such as chess and Go are idealised war games. In the
168early days of Artificial Intelligence (AI) research, chess was
169generally regarded as the intellectual challenge par excellence, and
170many efforts were made to apply Operations Research principles to it.
171Of course, there was the usual spectrum of futurologies, but no-one,
172including Gordon Moore himself, imagined that his observation that
173computer power per square inch had doubled every couple of years
174would continue to be true for so long, and certainly not that raw
175power would be sufficient to knock Chess Grandmasters off their
176pedestals.
177</P>
178<P>On average, there are around 20 legal moves in a chess position.
179So to look ahead 7 steps (this number has been chosen for a reason,
180which will be explained in a minute), a brute force chess program
181would need to consider 20<SUP>7</SUP> = 2<SUP>7</SUP> x 10<SUP>7</SUP>
182= 128 x 10<SUP>7</SUP> = about 10<SUP>9</SUP> positions - rather a
183lot, but not beyond the capability of modern computer chips, which
184can perform a calculation in as little as 10<SUP>-?</SUP> seconds.
185</P>
186<P>By 1973, a celebrated mathematician was commissioned by the
187British Government to assess whether it was worthwhile to invest in
188the then newly-emerging research field of Artificial Intelligence
189(AI). He correctly observed that almost every problem AI people were
190tackling had the inherent character of dealing with a &quot;combinatorial
191explosion&quot; of possibilities - but he incorrectly concluded that
192it would therefore be a waste of public money to sponsor AI research.
193His recommendations were eagerly accepted by the fiscally myopic
194government of the day, causing many of the top British AI scientists
195to leave the country.
196</P>
197<P>That debacle is long past, but the essential problem remains: the
198inherent possibility space for many problems, including Go, is indeed
199vast, and AI scientists are still only just beginning to scratch the
200surface of a solution anywhere near as effective as that which took
201Nature several billion years to evolve - our brains. And when we say
202&quot;our&quot;, we don't just mean humans, but all animals.
203</P>
204<P>In the years since 1973, AI researchers, cognitive scientists and
205neurophysiologists have started to work together to figure it all
206out. Some remarkable facts are being discovered. Such as that many
207tasks like medical diagnosis that we always had believed require
208especially intelligent witchdoctors to perform successfully turn out
209to be a lot less complicated than we thought, and a lot of apparently
210ordinary tasks like recognising people are enormously more
211complicated than we ever realised and more complex (in terms of the
212size of their possibility space) than medical diagnosis (with
213present-day knowledge of how the body works).
214</P>
215<P>At the same time, the remarkable progress in developing computer
216power has cast a new light upon the intellectual demand of chess. In
2171997, a computer called Deep Blue defeated an astonished world
218champion Gary Kasparov. The rest is history. Murray Campbell, the
219creator of Deep Blue, remarked in an interview with the online
220magazine &quot;Wired&quot; on May 11, 2007: &quot;It's almost the end
221of the story for chess in the sense that matches between chess
222machines and grand masters are becoming less interesting because it's
223so difficult for the human grand masters to compete
224successfully....The current world champion, Vladimir Kramnik from
225Russia, lost a match to a PC program in November, 4-2&quot; 
226</P>
227<P>It is striking that Go programs lag far behind their chess
228brothers. But it doesn't take a genius to work out why - <BR>(1)
229although both games are played on a board, with a fixed number of
230places, and a fixed number of kinds of pieces (only one in the case
231of Go), there is one key difference: there are 8 x 8 = 64 places in
232chess and 19 x 19 = 361 in Go. The Go board is about 6 times as big
233as a chess board, but the Go tree is rather more than 6 times the
234size of the chess tree.... at each step in a lookahead, there are 10
235times as many choices. With 7 steps, there are 10<SUP>7</SUP> =
23610,000,000 times as many things to look at. So it would take the same
237computer 10,000,000 times as long to make a move in a Go game as it
238would to make a move in a chess game! <BR>(2) The ability of a
239game-playing computer is measured by its performance against people.
240</P>
241<P>We will look at both of these things, and in so doing we will
242discover some key insights into the very nature of intelligence.
243</P>
244<P>...........
245</P>
246<P>Whereas it is certainly true that a camel is a horse designed by a
247committee, GNU software is not as bovine as a gnu. Rather, it is as
248smart as an Internet &quot;wiki&quot;, which represents the
249consolidated collective knowledge of many sorcerers put together
250asynchronously over a long period of time - far different from the
251usually cumbersome, clumsy and crude compromises made by committees
252of self-interested carpetbaggers in their haste to get away from the
253meeting room and back onto the golf course - Charles de Talleyrand
254hit the nail exactly on the head when he observed: &quot;A Court is
255(nothing more than) an assembly of noble and distinguished beggars&quot;.
256His observation remains as true today as it was in 1798, for people
257have evolved little in the last 100,000 years or so since they first
258fell out of the trees.
259</P>
260<P>GNU Go side-steps the full-board search combinatorial explosion
261issue by restraining its imagination to moves associated with locally
262tactical objectives such as captures, life &amp; death of groups, and
263connection reading. It makes a rough estimate of the balance of
264territory at the end of each lookahead sequence which is used as the
265means of ranking alternatives.
266</P>
267<P>more to come
268</P>
269<H2>--------------------------------------------------------------</H2>
270<P><FONT SIZE=4 STYLE="font-size: 16pt"><B>Interweaving Strategy and
271Tactics in Gnu Go </B></FONT>
272</P>
273<P><BR><BR>
274</P>
275<P>DJH Brown,
276</P>
277<H2><BR><BR>
278</H2>
279<P>Abstract
280</P>
281<H2><BR><BR>
282</H2>
283<P>Introduction
284</P>
285<P>a picture is worth a thousand words
286</P>
287<P>etc
288</P>
289<H2><A HREF="http://trac.gnugo.org/gnugo/wiki/ArticlesOnGnuGo#a6">--------------------------------------------------------------</A></H2>
290<P><STRONG><FONT SIZE=4 STYLE="font-size: 16pt">Other suggestions</FONT></STRONG><FONT SIZE=4 STYLE="font-size: 16pt">
291</FONT>
292</P>
293<P STYLE="margin-bottom: 0in"><BR>
294</P>
295</BODY>
296</HTML>