Jeremy
Bentham
- seeker of happiness
Community-authored articles on Gnu Go for publication elsewhere
Your contributions welcomed. Please just edit the text and add your name to the alphabetically ordered list of authors. Or email me djhbrown@gmail.com something or point me to somewhere and i will work it in if i can.
Worms, Dragons and Owls: How GNU Go Works
DJH Brown, nando8888,
Not so long ago, chess was generally regarded as the intellectual challenge par excellence, but in the last 10 years, things have changed. Murray Campbell, the father of Deep Blue, the computer that defeated Gary Kasparov in 1997, recently remarked in an interview with the online magazine "Wired": "It's almost the end of the story for chess in the sense that matches between chess machines and grand masters are becoming less interesting because it's so difficult for the human grand masters to compete successfully....The current world champion, Vladimir Kramnik from Russia, lost a match to a PC program in November, 4-2"
Chess programs use a basic technique which operates as follows:
Some way of figuring out what is going on in a position is used to
(a) make an assessment of which player is winning and by how
much, and
(b) decide which moves might favour the player whose
turn it is.
A "lookahead" algorithm is used to imagine sequences of moves following on from each considered alternative move. The imagined most likely ultimate state of play - as adjudged at the end of each imagined sequence by the position evaluator mentioned in 1(a) and considering all imagined follow-up sequences - is regarded as the expected outcome of that alternative move, and hence its utility to the player.
The best (ie highest ranked) alternative move is chosen.
As there are several alternative moves at each step in the lookahead, the different lines together create what computer programmers call a "search tree" (because if you drew it out on a piece of paper, starting at the top of the page and writing down the alternative moves underneath, and underneath that their responses, and so on, it would look like an upside-down tree). The imagined most likely ultimate state of play deriving from each alternative is calculated by the heuristic assumption that the opponent is using the same kind of mechanism, and will choose his (her) most favourable move at each stage.
There are various techniques the lookahead algorithm can employ to make its search efficient, but there is a fundamental problem: the size of the lookahead tree is an exponential function of the number of alternative moves at each step. At each turn, there are on average around 20 possible moves in chess and around 200 in Go. So to look ahead 7 steps, a brute force chess program would need to consider 207 = 27 x 107 = 128 x 107 = about 109 positions - rather a lot, but not beyond the capability of modern computer chips, which can perform an arithmetic calculation in as little as 10-9 seconds.
However, although the Go board is only 6 times as big as a chess board, the Go tree is rather more than 6 times the size of the chess tree.... at each step in a lookahead, there are 10 times as many choices. With 7 steps, there are 107 = 10,000,000 times as many things to look at. So it would take the same computer 10,000,000 times as long to make a move in a Go game as it would to make a move in a chess game!
This makes programming a computer to play Go a fascinating challenge. A lengthy description of some (but not all!) Go programming difficulties can be read at http://en.wikipedia.org/wiki/Computer_Go. One thing is for sure: the technique used by chess programs simply cannot work effectively for Go.
GNU Go is an open collective effort by members of GNU, a nonprofit organisation that creates software for Unix-based computers. Its official documentation can be read at http://www.gnu.org/software/gnugo/gnugo.html Whereas it is probably true that a camel is a horse designed by a committee, GNU software is not as bovine as a gnu. Rather, it is as smart as an Internet "wiki", which represents the consolidated collective knowledge of many sorcerers put together asynchronously over a long period of time. Many GNU Go "robots" are signed up on Internet Go servers for people to play against; they are ranked at around 5k. Gnu Go was runner-up to KCC in the 2006 World Computer Go Championship; tournament information can be viewed at http://computer-go.softopia.or.jp/gifu2006/English/
......introduce worms etc GNU Go uses a variety of techniques to select and read out moves associated with locally tactical objectives such as captures, life & death of groups, and connections. It makes a rough estimate of the balance of territory at the end of each lookahead sequence which is used as the means of ranking alternatives.
more to come
Playing for Keeps
DJH Brown,
Jeremy
Bentham
- seeker of happiness
And once upon another time, shortly before World War I, the Prussian army achieved remarkable military successes against larger forces due to its use of simulated war scenarios to "tank-test" alternative battlefield tactics. This fostered interest in what came to be known as "Operations Research", which has been nurtured by (and possibly even partly responsible for) every major international conflict - including so-called free market competition - ever since.
Given their very different origins and purposes, Utility Theory and Operations Research may seem strange bedfellows, and yet, they are ideal partners. Operations Research concerns itself with methods of identifying an optimal outcome, and Utility Theory provides a mechanism for measuring outcomes.
Moore's
Observation
Board games such as chess and Go are idealised war games. In the early days of Artificial Intelligence (AI) research, chess was generally regarded as the intellectual challenge par excellence, and many efforts were made to apply Operations Research principles to it. Of course, there was the usual spectrum of futurologies, but no-one, including Gordon Moore himself, imagined that his observation that computer power per square inch had doubled every couple of years would continue to be true for so long, and certainly not that raw power would be sufficient to knock Chess Grandmasters off their pedestals.
On average, there are around 20 legal moves in a chess position. So to look ahead 7 steps (this number has been chosen for a reason, which will be explained in a minute), a brute force chess program would need to consider 207 = 27 x 107 = 128 x 107 = about 109 positions - rather a lot, but not beyond the capability of modern computer chips, which can perform a calculation in as little as 10-? seconds.
By 1973, a celebrated mathematician was commissioned by the British Government to assess whether it was worthwhile to invest in the then newly-emerging research field of Artificial Intelligence (AI). He correctly observed that almost every problem AI people were tackling had the inherent character of dealing with a "combinatorial explosion" of possibilities - but he incorrectly concluded that it would therefore be a waste of public money to sponsor AI research. His recommendations were eagerly accepted by the fiscally myopic government of the day, causing many of the top British AI scientists to leave the country.
That debacle is long past, but the essential problem remains: the inherent possibility space for many problems, including Go, is indeed vast, and AI scientists are still only just beginning to scratch the surface of a solution anywhere near as effective as that which took Nature several billion years to evolve - our brains. And when we say "our", we don't just mean humans, but all animals.
In the years since 1973, AI researchers, cognitive scientists and neurophysiologists have started to work together to figure it all out. Some remarkable facts are being discovered. Such as that many tasks like medical diagnosis that we always had believed require especially intelligent witchdoctors to perform successfully turn out to be a lot less complicated than we thought, and a lot of apparently ordinary tasks like recognising people are enormously more complicated than we ever realised and more complex (in terms of the size of their possibility space) than medical diagnosis (with present-day knowledge of how the body works).
At the same time, the remarkable progress in developing computer power has cast a new light upon the intellectual demand of chess. In 1997, a computer called Deep Blue defeated an astonished world champion Gary Kasparov. The rest is history. Murray Campbell, the creator of Deep Blue, remarked in an interview with the online magazine "Wired" on May 11, 2007: "It's almost the end of the story for chess in the sense that matches between chess machines and grand masters are becoming less interesting because it's so difficult for the human grand masters to compete successfully....The current world champion, Vladimir Kramnik from Russia, lost a match to a PC program in November, 4-2"
It is striking that Go programs lag far behind their chess
brothers. But it doesn't take a genius to work out why -
(1)
although both games are played on a board, with a fixed number of
places, and a fixed number of kinds of pieces (only one in the case
of Go), there is one key difference: there are 8 x 8 = 64 places in
chess and 19 x 19 = 361 in Go. The Go board is about 6 times as big
as a chess board, but the Go tree is rather more than 6 times the
size of the chess tree.... at each step in a lookahead, there are 10
times as many choices. With 7 steps, there are 107 =
10,000,000 times as many things to look at. So it would take the same
computer 10,000,000 times as long to make a move in a Go game as it
would to make a move in a chess game!
(2) The ability of a
game-playing computer is measured by its performance against people.
We will look at both of these things, and in so doing we will discover some key insights into the very nature of intelligence.
...........
Whereas it is certainly true that a camel is a horse designed by a committee, GNU software is not as bovine as a gnu. Rather, it is as smart as an Internet "wiki", which represents the consolidated collective knowledge of many sorcerers put together asynchronously over a long period of time - far different from the usually cumbersome, clumsy and crude compromises made by committees of self-interested carpetbaggers in their haste to get away from the meeting room and back onto the golf course - Charles de Talleyrand hit the nail exactly on the head when he observed: "A Court is (nothing more than) an assembly of noble and distinguished beggars". His observation remains as true today as it was in 1798, for people have evolved little in the last 100,000 years or so since they first fell out of the trees.
GNU Go side-steps the full-board search combinatorial explosion issue by restraining its imagination to moves associated with locally tactical objectives such as captures, life & death of groups, and connection reading. It makes a rough estimate of the balance of territory at the end of each lookahead sequence which is used as the means of ranking alternatives.
more to come
Interweaving Strategy and Tactics in Gnu Go
DJH Brown,
Abstract
Introduction
a picture is worth a thousand words
etc
Other suggestions