Artificial Intelligence

and

Go

 

 

 

 

 

Neal Winterhof

Minds and Computers

12/8/00

 

 

            “…this game may have to replace chess as the ‘task par excellence’ for AI.”

–        Hans Berliner

 

“The research of Go programs is still in its infancy, but we shall see that to bring Go programs to a level comparable with current chess programs, investigations of a totally different kind than used in computer chess are needed.”

                                                                                    – John McCarthy

BACKGROUND

In order to understand Go and its future in artificial intelligence, a brief background of its history should first be examined.  Go is arguably the oldest game still played in its original form having been created about three thousand to four thousand years ago in ancient China.  Its true origins are still unclear as speculation states that Go, originally called Wei Qi in Chinese which literally means “surrounding game”, may actually have been a forerunner to the abacus or even an early fortune-telling device (“A Very Brief History of Go”).  Legend speculates that the first emperor of China created the game to improve the intelligence of his dull-witted son and mythology stories a tale where a Buddhist ruler challenged an aggressor to a game of Go to determine the future of Tibet so that no bloody war would take place.  Go was and still is widely regarded as a game requiring superior intelligence that everyone from Chinese gentlemen to military generals played to show off their skills and hone their military tactics and strategy.  Go was even considered one of the “Four Accomplishments” (brush painting, poetry, and music being the other three) that distinguished a gentleman in Chinese society (“A Very Brief History of Go”).  Go gradually spread throughout Asia, reaching Japan in the first century AD.  It was there that Go became modernized with the establishment of special Go teaching schools and the development of a ranking system for expert, professional players.  Go further made its way to Korea and eventually to Europe and the United States where Go is still slowly gaining popularity.  However, it has long been understood that the best Go is still played in Asia where intense professional competition in and between China and Japan has spurred the existence of million dollar sponsored annual tournaments that are followed as closely as the World Series is in the United States.

 

COMPARISON TO CHESS

Go is a game that is similar in many respects to chess, but yet, it transcends the game of chess in many ways.  By their very nature, both are games of strategy that utilize human intelligence, inference, and instinct to problem-solve strategies in order to defeat one’s opponent.  It may at first seem easier for a computer to master Go, because all the player’s pieces are identical and the board is empty at the beginning of the game whereas chess requires two armies of pieces that have different values and move capabilities.  However, for a computer, Go is incredibly harder.  “It may be a hundred years before a computer beats humans at Go – maybe even longer.  If a reasonably intelligent person learned to play Go, in a few months he could beat all existing computer programs.  You don’t have to be a Kasparov[world chess champion].” (Johnson)  Subsequently, it leads one to ask just what makes Go so much harder than chess.

The answer to such a question is fairly simple: the brute-force searching method employed by computer chess programs is ineffective and useless in the game of Go.  Although Deep Blue’s defeat of the reigning world chess champion Garry Kasparov signaled a great triumph in the field of artificial intelligence, it can be argued that Kasparov only lost to a very smart calculator.  Deep Blue is a beast in both the physical and chess-playing sense; it is a version of the IBM RS/6000 supercomputer that weighs 2,800 pounds and is capable of calculating 200 million positions per second.  On the other hand, it has been estimated that Kasparov can only evaluate three positions per second.  Thus, the pure computational speed and ability of Deep Blue is able to compensate for its lack of human intuition and reasoning that Kasparov utilizes to examine the intricate details of game.  Consequently, Deep Blue is a highly specialized computer that only uses brute force to play chess; consequently, it is argued that Deep Blue’s overall intelligence is only comparable to that of a three year old, which is not enough for the game of Go (Eisenberg).

In fact, if a computer with Deep Blue’s abilities tried to play a game of Go against an expert Go player, it would probably get beaten like a three year old for this reason: the game of Go is numerous times more complex than chess and for this reason, the brute force method becomes highly inadequate to account for all the possible moves.  The branching factor, which accounts for all the possible future game states, is incredibly deeper and more complex in Go.  Whereas in chess, a player has an average of 35 legal moves, Go players have an average of 200 possible moves.  In chess, there are constraints on the pieces as to where they can move (even more constraints if the computer can weed out purely “stupid” moves), however, because Go[1] starts out with an empty board, the first player can put his piece in any of 361 places, the second player in any of 360 places and so on (Johnson).  Thus, the branching factor becomes immense in Go; a computer that looks ahead four moves in chess would require looking through, on average, 35⁴ or about 1.5 million board positions compared to 200⁴ or 1.6 trillion board positions for Go, not to mention that that number is greatly increased at the beginning of the game(361 x 360 x 359 x 358). 

Source: “Kasparov, Deep Blue, and the Games Machines Play”

 

Furthermore this example truly indicates just how far artificial intelligence still has to come in Go.  In chess, a computer must “look ahead” to determine the success rating of each possible move by examining possible countermoves to a move, possible countermoves to that countermove, and so on.  Each examination of a move and its possible countermove is called a ply.  Deep Blue can look ahead about 7 to 8 plies, or about fifteen moves ahead.  Applied to Go, when asking the computer to look ahead fifteen moves in Go, the computer is faced with a branching factor of 200¹⁵ possible board positions compared to only 35¹⁵ in chess.  Further still, if the similar pruning techniques used by Deep Blue are used in Go to eliminate clearly futile tree branches, then “a Go computer as fast as Deep Blue (which analyzed some 200 million chess positions per second) would take a year and a half to mull over a single move.” (Johnson) Thus, it becomes glaringly evident that Go poses a much greater obstacle than at first thought.

 

CURRENT GO PROGRAMS

Although computer Go programs have seen progress in recent years, it still has a long way to go.  Today, the best computer programs are able to give the average amateur Go player a good game; this can be seen as positive progress considering the complexity that arises out of the game or as only trivial gains burdened by the shear amount of improvement that is still need.    Whatever the case, increased interest and fascination with computer Go programs is clearly evident throughout the world.  The International Computer Go Congress, founded in 1985, along with other research foundations, have served to promote the advancement of computer Go programs through big international tournaments as well as the emergence of computer Go ladders on the internet.  Thus, such initiative and motivation has created an environment conducive to the propagation of artificially intelligence Go programs, however, the effectiveness of existing programs and support for new research has slowed and become somewhat stale.

There are many critics of current approaches to developing an artificially intelligent Go player stating that revolutionary new techniques need to be implemented if any real progress is to be made.  However, new modes of research have seemed to stall, because “few individuals or institutions have enough resources to subscribe to a full-scale Go programming effort.”(qtd. in Muller 3) The overhead of starting new Go projects and research is so overwhelming, because most new Go programs are started from scratch and require five to ten years in order to produce a competitive program.  Consequently, compared to chess, the support and resources devoted to Go programs is lacking, despite the fact that computerized Go is a tremendously more complex and difficult task to undertake. (Muller 3)

            Furthermore, the prevalent Go programs that are currently in existence have also faced increased criticism from skeptics.  It is said that these Go programs may make good moves during a game, but they possess one fundamental problem: they do not capture the true spirit of Go – that is, although they may make good moves, they possess no real understanding of the game which inevitably becomes apparent sooner or later in the course of a game. (Muller 4)  Currently, computer Go programs do not have the ability to learn and thus, their lack of adaptation makes them vulnerable in the long run.  For example, computer Go programs often initially take advantage of a player unaccustomed to playing against a computer in the first few games; however, the computer’s weaknesses soon become apparent and the human is able to exploit the computer’s deficits.  This may be the consequence of the fact that no current computer Go program is able to incorporate all the computer Go tactics and strategies currently being employed.  Thus, critics would say that each program is incomplete in a sense, and perhaps, the key to creating a dominant Go player is through the integration of all the existing models for computer Go players.  So then, one may ask what are the existing models for current Go programs?

 

TRADITIONAL AI APPROACHES TO GO

            Artificial intelligence has utilized many approaches thus far to create an intelligent Go program. Two of the most fundamental features of today’s Go programs are knowledge representation and game tree search analysis, both of which were key components in Deep Blue.  In general, knowledge representation in artificial intelligence attempts to define aspects of a given problem into quantifiable and solvable element.  For example, board representation is necessary for the simple reason that a computer needs to be able to interpret or “understand” the environment in which the game is played.  Secondly, search algorithms and game tree development are pillars to gaming AI, because they, for example, provide the methods for determining all possible moves and ultimately deciding on the best possible move.  Both of these approaches can be found, in one form or another, in all computer Go programs.

            “Go sends investigators back to the basics--to the study of learning, of knowledge representation, of pattern recognition and strategic planning. It forces us to find new models for how we think, or at least for how we think we think.” (Mechner)  Go research has focused mainly on knowledge representation and in the development of a hierarchal model for information processing; the program processes low level concepts, such as the determining where the pieces are on the board, to infer higher level concepts such as pattern recognition.  In fact, many programmers believe that truly intelligent Go programs will eventually arise from this pattern recognition approach.

            Pattern recognition is one of the more advanced techniques of knowledge representation.  As human players become better and more experienced, they develop their own knowledge base of instantly recognizable patterns of stones from which they can easily make successful moves.  For example, consider the following two board positions:

      

Figure 1: Black to Play                                           Figure 2:Keima Relationship

Source: “Architecture for Computer Go”                                                                                                                                                                        

For human players experienced in the Go, Figure 1 is an easily recognizable configuration of stones where x marks the most effective next move.  Furthermore, the relationship of stones in Figure 2 is called a Keima relationship that is similarly easily recognizable.  Together, these are two examples where not only knowledge of the next best possible move, but also knowledge about the most likely follow-up moves gives the player a distinct advantage in the game (Mechner).  However, the key is being able to apply such a knowledge base to a computer.

            The fundamental concept of developing a knowledge base for a computer Go player is in building pattern recognition and positional analysis. Once a computer is able to recognize reoccurring patterns in a game, it can then easily infer possible subsequent moves from its knowledge base and thus, gain crucial insight to the game.  Furthermore, Go programmers have started working on what is called incremental knowledge maintenance which is essential the active accumulation of knowledge as the game progresses (Mechner).  For example, a human player is able to update his “knowledge” of the game by tracking various patterns of stones and say to himself: “I don’t have to worry about it unless my opponent plays in this area.”  Thus, it allows the human player to be constantly informed of the overall state of the game board.  Applied to computers, incremental knowledge maintenance will allow a computer to use their resources more efficiently by ignoring areas of the board that have no direct influence on the game.   Thus, “by applying pattern knowledge and accumulated positional knowledge, a player is able to exclude bad moves from consideration and quickly recognize and stop exploration in hopeless positions.” (Mechner) In terms of Go, knowledge representation is paramount and fundamentally begins with pattern recognition.

Figure 3: Mini-Max Searching

Very few board games are one player, so how can we add this into our tree?

Think about it, when we are playing for ourselves we are attempting to maximize our score, so our opponent will want to minimize our score. Let us look at a game tree - this one though is limited to a depth of 2. Here is our game tree with evaluations assigned to the final nodes:

Now, the assigned values are for boards representing our opponents choice of boards. N1 stands for the current board, N2-N4 are our three possible moves and N5-N13 are the opponents possible follow-up moves. Since our opponent will try to minimize our winning possibility^*, therefore will calculate the minimum value for each node and assign it to the parent. N2 will equal 0, N3 will equal 3, N4 will equal 2. In making a choice for our best possible move, we look at the maximum of these values - which is 3 (N3).

Taken directly from “Minimax Trees”

 

Consequently, there are three kinds of searches employed by computer Go players: single-goal, multiple-goal, and full-board searches (Muller).  Specialized searches are key to Go programs, because full board searches, also known as global searches, of all possible moves are virtually impossible due to its immense complexity.  Single-goal (i.e. finding possible moves for the sole purpose of surrounding an opponents stone) and multiple-goal (i.e. working toward surrounding a particular stone, but still maintaining control in another part of the board) searches provide a thorough investigation of all relevant moves that eventually aid in the global decision making process thereby producing the most successful move.  Although searching can be a very useful tool, searching will always be limited even with the constantly improving technology that is making computers faster and more powerful for this simple reason: computer Go players that use searching are essentially using brute force to play the game and thus, they possess no real understanding of the game.

 

NEURAL NETWORKS

            Although most of today’s Go programs rely on more traditional approaches such as knowledge representation and positional analysis, new approaches are beginning to arise that involve neural networks.  The Academic Press Dictionary of Science and Technology defines neural networks[2] to be “a computational network, often for pattern recognition, composed of mathematically defined elements that are thought to approximate the working of biological neurons; often composed of a layer that receives and organizes inputs, a hidden layer, and an output layer in which individual neurons identify particular patterns.”  To put it simply, in the context of Go, a neural network will interpret a given input (a particular game state), process the input through the activation and inhibition of neurons, or nodes, in its network, and ultimately output the best possible move.  There are two intriguing methodologies to utilizing neural networks: 1) Self-sustaining neural networks that employ temporal difference learning and 2) the integration of an expert system with a neural network.

            The newest computer Go networks use a temporal difference algorithm[3] with reinforcement learning to produce the most “intelligent” Go player. (Schraudolph, Dayan, and Sejnowski)  This approach simply means that the neural networks are able to train themselves by observing various input game states, examining the effectiveness of their move, and then “remembering” whether it was a good of bad move for future reference.   The training of these neural networks take advantage of the fact that board positions in Go are translation-invariant and as such, are able to easily recognize, define, and manipulate various patterns of stones.  This means that the value of a certain configuration of stones on the game board is universal; all things being equal, it does not matter where on the board a certain configuration appears, because they are worth the same (Scott).   With this knowledge, a computer need only to recognize the pattern of stones and can essentially ignore their position on the board, thereby making its job much easier

The neural network can be effectively divided into three levels: an input layer, hidden layers responsible for positional analysis, and an output layer that makes the best move based on the input of its subordinate layers.  The initial input layer of the neural network reads the given game state and translates it into “neuron language” by breaking it down into the individual activation and inhibition of its nodes.  The hidden layers are “feature detectors” that are able to interpret the game state and distinguish important stone configurations.  However, if new stone patterns are discovered, the network is able to incorporate that knowledge into its system by retraining its neurons; thus, it is able to learn and accumulate experience as it plays.  The actual training of neurons occurs as

the result of the reinforcement learning mechanism which is essentially a feedback loop that lets the program know the success of a move.  The last layer evaluates the inputs it receives from the hidden layers and then decides on the best move.  Overall, the system mimics information processing in brain, because the network is able to transduce a given input(a game state), process the information (find important stone configuration), and output the most appropriate reaction (yielding the best move).

            The actual training of these Go playing neural networks was also very interesting.  It became evident that the network learned fastest when playing a moderately stronger opponent.  Training against similarly skilled opponents and through self-play (playing itself) was slow and relatively unproductive, because no significant “learning” could take place.  At first, the network played against the weakest opponents, because it has no knowledge base from which to start, but it caught on quickly.  However, this neural network approach is still in its infancy; although it has defeated a relatively strong commercial program, called the Many Faces of Go, in a simpler 9 x 9 dimension board, the network is still too slow for a full game of Go on a 19 x 19 intersecting board (Scott).

            Another interesting approach to computer Go is incorporating an external expert system with a neural network.  The structure of such a program is actually fairly simple to conceive.  The first step transforms the game state into configurations of stones and empty intersections that is understandable by the system.  From there, the transformed Go position is sent to three different specialized expert systems that evaluate the information.

Figure from “Integration of a Priori Knowledge into a Go Playing Neural Network”

 

 The relation expert and the feature expert essentially work together to form the most efficient and accurate analysis of stone configuration and board patterns.  The feature expert functions similarly to a normal computer Go neural network; however, the relation expert gives the system an added perspective by recognizing the translational invariances of patterns on the board and relating the strategic significance of a particular stone configuration with its neighboring stone configurations.  Basically, the relation expert puts recognized patterns of stones into the context of whole board, so the system is able see the interplay between various stone configurations and not just limit itself by focusing on one particular pattern of stones.  The external expert is a separate algorithm that evaluates the board independently of the other two experts.  It can be a basic search algorithm that is able to offer good moves in a simplified situation where a logical move is easily deducible.  The final step is the overall evaluation of the proposed moves, so that only the best possible move will be made.  Overall, the integration of a neural network with an expert system provides a self-check mechanism to ensure that the program doesn’t overlook anything, but perhaps more importantly, the system, when taken as a whole, gains a better understanding of the more intricate details of the game thereby making it a better player (Enzenberger).

 

CONCLUSION

            Some people say that creating an artificially intelligent Go player is the final frontier in AI while other say that it is just another step in a long journey toward truly intelligent machines; either way, it signifies an immense challenge that may or may not be achieved.  The game of Go can be seen as an enigma, because although it appears as a simple game (only one type of piece; either black or white at an intersection; no dice, elements of chance, or hidden aspects to the game) compared to chess, it has been shown to be an extraordinarily more difficult game to master.  The critics of computerized Go players say that Go will never be mastered by any machine, because it is a game that truly engages the human intellect, whose true nature is not reproducable in artificial machines.  They debate that even though chess is a clearly a game of intellect, Deep Blue is not a truly intelligent machine – it is only a very smart, specialized, and powerful calculator that only exhibits the appearance of intelligence through brute force. 

There exists a saying that states true genius and intellect is being able to get from A to D without going through B and C.  However, computers must meticulously examine B and C, because they lack the intuition that comes with human intelligence.  Thus, these critics argue you cannot quantify the true nature of human intelligence, because it is an instinctive, intuitive, and  inherent process.  However, strong AI enthusiasts say that no matter how exceptional human intelligence may appear, it is still founded on purely biological bases that can be recreated, for example, in neural networks.  Who is right?  Well, that is for each individual to decide, but perhaps the ultimate judge is time, because only time will tell where AI will take us.

Although the philosophical debate will continue to rage on as to whether artificial intelligence will ever conquer the game of Go, there exists a very real prize for such a possibility.  Founded and named for the Taiwanese businessman who died in 1997, the Ing Foundation seeks to promote the game of Go and offer the Ing Cup, a one-million dollar prize to the computer Go program that can defeat a human Go master.  Entrants from all over the world still complete for this unclaimed prize.  However, it appears that this prize will remain unclaimed for quite some time.

 Mr. Ing

 

The Ing Cup as well as Deep Blue’s recent defeat of Garry Kasparov has raised fascination and increased awareness about computer game programs and artificial intelligence in general.  The possibilities and potential of AI may be endless, because research and technology has enabled, for example, Deep Blue to achieve that which was once thought impossible – beating the world chess champion.  However, others argue that AI may have hit an impossible impasse with Go, because Go is a truer measure of intelligence.  There are no clear answers as to where the future of AI will lead, nor should we expect any such answers.  If a computer Go program is able to beat the world Go champion, will critics concede that artificial intelligence, in its most genuine form, has been achieved or will the bar only be raised further and another game that is better test of intelligence be found to replace Go – only time will tell.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Appendix

 

http://www.gatsby.ucl.ac.uk/~dayan/papers/sds00.pdf

 

http://www-dse.doc.ic.ac.uk/~nd/surprise_96/journal/vol4/cs11/report.html

 

http://www.yutopian.com/go/goLes/howtogo.pdf

Works Cited

 

 

“Computer Go.” Online. Accessed 13 November 2000. Online. <http://www.usgo.org/computer/>.

 

Eisenberg, Bart. “Kasparov, Deep Blue, and the Games Machines Play.” Pacific Connection. Online. Accessed 13 Novemver 2000. <http://www.gihyo.co.jp/SD/pacific/SD_9708.html>.

 

Enzenberger, Markus. “The Intelgration of a Priori Knowledge into a Go Playing Neural Network.” Online. September 1996. Accessed 13 November 2000. <http://www.cgl.ucsf.edu/home/pett/go/Programs/neurogo-html/NeuroGo.html>.

 

“Introduction to the Game of Go.” Online. 6 December 2000. <http://www.britgo.org/intro/intro1.html>.

 

Johnson, George. “To Test a Powerful Computer, Play an Ancient Game.” New York Times Online. Online. 29 July 1997. Accessed 13 November 2000. <http://www.math.ntnu.no/~henning/gin/media/nytimes.html>.

 

Klinger, Tim and David Mechner. “An Architecture for Computer Go.” Online. Accessed 6 December 2000. <http://www.cns.nyu.edu/~mechner/compgo/acg/acg.html>.

 

Mechner, David. “All Systems Go.” Online. 6 December 2000. <http://www.cns.nyu.edu/~mechner/compgo/sciences/>.

 

McAdams, Mindy. “What is Go?” Online. 6 December 2000. <http://www.well.com/user/mmcadams/gointro.html>.

 

“MiniMax.” Generation⁵. Online. Accessed 6 December 2000. <http://www.generation5.org/minimax.shtml>.

 

Schraudolph, Nicol, Peter Dayan, and Terrence Sejnowski. “Learning to Evaluate Go Positions via Temporal Difference Methods.” Online. Accessed 6 December 2000. <http://www.gatsby.ucl.ac.uk/~dayan/papers/sds00.pdf>.

 

Scott, Jay. “Nici Schraudolph’s Go Networks.” Online. 14 June 1998. Accessed 13 November 2000.

<http://forum.swarthmore.edu/~jay/learn-game/systems/go-net.html>.

 

Stergiou, Christos and Dimitrios Siganos. “Neural Networks.” Online. Accessed

6 December 2000. <http://wwwdse.doc.ic.ac.uk/~nd/surprise_96/journal/vol4/

cs11/report.html#What is a Neural Network>.

 

Tesauro, Gerald. “Temporal Difference Learning and TD – Gammon.” Online. Accessed 6 December 2000. <http://www.research.ibm.com/massive/tdl.html#h1:temporaldifferencelearning>.

 

“Very Brief History of Go.” Online. 6 December 2000. <http://www.usgo.org/resources/gohistory.html>.