Developments in computer Baduk



Developments in computer Baduk

Łukasz Lew

Department of Computer Science,

Warsaw University, Poland

e-mail: lew@mimuw.edu.pl

INTRODUCTION

In most board games humans are dominated by computers. Despite a huge amount of work Baduk still remains the last popular board game where computer play is still weak.

The usual Artificial Intelligence approach for game playing consists of a global search algorithm and a procedure evaluating the goodness of a position. This does not work in Baduk. A global search is impossible because the rules of Baduk do not put a lot of constraints on the players thereby allowing an astronomical number of possible combinations. But even when search is possible, for instance on a 9x9 board, a good way of evaluating the position is not known. It is so difficult because Baduk positions have a very rich and diverse structure. Situations appearing on the board can have a lot of subtlety, and may be in a state of fragile equilibrium, especially in high level games.

This diversity, complication and deepness are features that distinguish Baduk from other board games. For the same reasons Baduk is considered the greatest challenge for Artificial Intelligence among all the games.

This article consists of two parts. First part shortly describes the history of computer Baduk and the construction of current state-of-the-art Baduk programs. I place special emphasis on a recently popular Monte-Carlo technique, which is amazing combination of simplicity and good performance (for computer Baduk standards).

The second part presents developments on particular sub-problems of Baduk, such as pattern systems, Life and Death, finding territory, etc. I place special emphasis on the pattern systems, because they are probably the most interesting and useful for a Baduk player.

PART I

I.1 Short history

The first computer Baduk program was created around 1970 by Zobrist [Zor71]. It was mainly based on computation of an influence radiated by the stones. Thanks to that it was able to beat a human (an absolute beginner) for the first time. At that time all the programs were based on different variations of the influence function.

The next important step was taken thanks to the analysis of human perception of Baduk [Rei75a, Rei75b]. Programs of that time started to use an abstract representation of a Baduk board and were able to reason about strength of groups. But probably the most significant breakthrough happened around 1990 [Boo90] when use of the pattern was widely adopted to recognize typical situations and to suggest moves.

Since then probably all top programs combine those three techniques, but little is known about the details of algorithms used, because most of the best Baduk software is commercial. Those programs were usually developed by a single programmer being simultaneously a Baduk player during a period of 5-15 years [Fot92, Fot93]. A notable exception is Gnu Go [Bum05] - a program from the Free Software Foundation written by a community of programmers.

From what is known most of State-of-the-art (non Monte Carlo) programs have the same basic framework: The backbone is a pattern-based move generator. Also, a lot of local tactical search determining a life status of strings, connection algorithms joining strings into groups are performed. Sometimes an influence function is calculated determining definite and potential territory. Sometimes shallow global search is run, but it is not obligatory. All the gathered pieces of information are used to choose a good move,

It is important to note that all the phases are filled with hand-coded knowledge in the form of heuristics and specialized algorithms. Usually, even the patterns, the most important component, are created manually. Such an approach is limited by the amount and the correctness of the knowledge introduced by the programmer.

I.2 Monte-Carlo Baduk

Recently a new technique, called Monte-Carlo Baduk attracted the attention of many researchers, because of its simplicity and very good results.

In general, Monte-Carlo algorithms are characterized by the fact that randomness is a substantial ingredient of their calculations. In the field of games it usually means that the algorithm plays a large number of simulations to explore characteristics of a large search space. This technique usually is used in imperfect information such as bridge [Gin99], poker [Bil02] or scrabble [She02]. In those games the randomness is used to model unavailable pieces of information. In stochastic games like backgammon [Tes97] Monte-Carlo is even more natural approach.

In deterministic, complete information games like Baduk this approach seems to be less natural. It is unclear what elements of a game should be random and why such an algorithm can obtain good results.

Historically, the first research on application of Monte-Carlo technique to 9x9 Baduk appeared in [Bru93]. Bruegmann's approach was remarkably simple. To choose a move, his program run several hundreds of playouts - completely random games to the bitter end. At the same time, for each legal move, the program maintained a statistic - an average of the results of those playouts, where this move occurred. Those averages were used as the estimates of moves' values. Eventually a move with the best value was played.

Bruegmann approach was followed by ten years later by Bruno Bouzy. Bruno made at least three contributions described in the following sections. In the fourth section I also describe a different approach to Monte-Carlo by Tristan Cazenave.

I.2.1 Combining Monte-Carlo program with a classical approach

Bouzy [Bou03a] set up Indigo2002 (a "classical" Baduk program he developed over a few years) as the move generator and the Monte-Carlo module as the move evaluator. This way, the Monte-Carlo module evaluated less than 10 moves instead of about 300 on a 19x19 board. Obviously moves considered tactically weak or bad for some reason by the Indigo2002 program were eliminated from evaluation.

This technique is named preprocessing. And its advantage of is improved speed allowing playing games on the 19x19 board in a reasonable time and reduction of a number of tactical blunders made by pure Monte-Carlo.

I.2.2 Monte-Carlo and patterns

The second contribution [Bou03a, Bou05b] is the use of a pseudo-random, biased playout, where probability of playing certain moves depends on their current (mid-playout) surroundings. To implement it, Bouzy used a database of 3x3 patterns manually built earlier for his program Indigo2002. Second bias for mid-playout move selection was detection of dansu which triggered captures with a probability proportional to the size of captured chain.

I.2.3 Monte-Carlo and tree search

The third contribution [Bou04] is the most influential one, as it is used in all good Monte-Carlo programs today. It is a combination of a global selective tree search with Monte-Carlo simulations.

Bouzy's original search algorithm - Progressive Pruning - is an ordinary global game tree searcher with following extensions. The depth of the tree is first set to one. When enough children are pruned, the algorithm extends the tree to the depth 2 by attaching to all not pruned leaves new children. Simultaneously, the algorithm performs random playouts starting from current tree leaves (not expanded nodes of the tree) and calculated average playouts' results. This average is used to value the leaves and to prune them, when some of them were found to be statistically inferior to some other leaf in the same branch. When the program is just about to choose a final move, then it uses a mini-max principle to propagate node values from leaves to the root and chooses the final move according to those values.

The combination of game tree search and Monte-Carlo was recently considerably improved [Cou06], and the strongest 9x9 Baduk programs of the day consist almost of this approach alone.

I.2.4 Monte-Carlo for sub-goal evaluation

Recently Tristan Cazenave proposed[Caz05] a way of integrating Monte-Carlo with specialized, search algorithms [Caz00, Caz02] used for evaluation of connection / disconnection, life / death, capture / escape or eye making / destroying. For each interesting goal, such as connection of two strings, he maintained a statistic - average result of those random Monte-Carlo playouts in which the particular goal was achieved. This way he was able to find the most valuable goals and generate the move, which achieved them. The strength of play of such algorithm was a much greater than any of its parts alone.

I.2.5 Conclusion

The last example is a completely different approach than all the previously described, because this time Monte-Carlo was not used to directly find the best move, but as an auxiliary procedure. It may show to the reader that Monte-Carlo, despite its simplicity is very flexible and still there is a lot that can be done.

PART II

Due to the difficulty and diversity of the task of automating Baduk play, many researchers concentrated on sub-problems of Baduk. This section will browse through the most important, in the author's opinion, results. It shows to the reader the diversity and broadness of sub-problems found in the Baduk and the great variety of existing approaches.

II.1 Pattern systems

Baduk is generally assumed to be a game where patterns play a major role. Full-board and especially corner openings are an obvious example, but good shape moves and many tactical moves are also typical pattern moves.

The purpose of a pattern system is to generate good moves for a given Baduk position. For a Baduk player this is probably the most interesting sub-problem, because such systems are very useful for assisting in game-analysis. Also pattern systems are usually the most important components of good Baduk programs.

II.1.1 Pattern system in Gnu Go

A very good example is an open source program - Gnu Go. Its pattern system is described in detail in [Urv02] and in the Gnu Go manual [Bum05]. The pattern matching algorithm is based on Deterministic Finite state Automata (DFA) and therefore it is very fast. The transition graph is created automatically from a database of manually edited patterns.

The patterns used in Gnu Go are very expressive and can provide detailed information about fuseki moves, possibilities of: attacking/defending and connecting/cutting a group, and endgame moves. The patterns also provide information about a group's eye-space and the way influence should be propagated through the board. The biggest bottleneck of the Gnu Go pattern system is that the patterns must be entered manually.

II.1.2 K-nearest-neighbors

An interesting approach is Bouzy's K-nearest neighbor algorithm [Bou05a]. He uses patterns only for suggesting the next move, but such a limitation makes it possible to harvest and value them automatically. The resulting system appears to be very flexible. The highlight of the paper is presented on diagram. The moves played in the opening of the game, which the system played against itself, have a very high quality and look like the moves played by a human.

II.1.3 Neural Network pattern system

A different approach was taken by Erik van der Werf [Wer02]. He proposes a neural network as a tool to recognize patterns and evaluate moves. He feeds the network with features of the position such as: location of nearby stones, proximity to the edge of the board, liberties before and after the evaluated move, possible captures, etc. The network is trained with a large number of high quality games. The results are very good - the system is able to predict 25% of the moves in previously unseen professional games.

II.1.4 Explicit pattern systems

In the previous system the knowledge is encoded in the weights of a neural network. In explicit pattern systems, the patterns are fixed in size and stored explicitly together with their ranking. Currently pattern systems with explicit patterns present the best performance in the field. There are two important pattern systems:

• MoyoGo [Gro06b] - where the system is integrated into a tool supporting Baduk player in analyzing games

• Bayesian Pattern Ranking [Ste05] - developed at Microsoft in cooperation with Cambridge University, available on Microsoft online Baduk server.

Pattern system used in MoyoGo was inspired by the research done by David Stoutamire [Sto91]. In turn, MoyoGo performance inspired David Stern, Ralf Herbrich and Thore Greapel

from Microsoft.

The main difference between those two systems is the algorithm used for creation of the database and the scale. Microsoft used a sophisticated Bayesian rating algorithm, while MoyoGo uses a very simple and robust algorithm. The scale difference is that Bayesian system includes over 12 millions patterns harvested and rated on 181,000 high quality games while MoyoGo includes over 16 millions patterns harvested and rated on over 500'000 high quality games.

Microsoft's pattern system is able to predict 34% of moves played in a professional game. This is quite an achievement compared to 25% of neural network described earlier. MoyoGo's performance is even better - it predicts 40% of moves. The following part describes MoyoGo pattern system.

There are 12 pattern sizes, from very small to the entire board. Each pattern includes:

1. The exact stone configuration inside the physical pattern perimeter, with an empty point in the middle and an indication which player should play there.

2. The exact distance to the edges of the board.

3. The Pae-status of the game.

4. The number of stones in all connected strings of stones adjacent to the patterns' center point.

5. The number of liberties of all connected strings of stones adjacent to the patterns' center point.

6. The urgency value (rating).

The pattern system was constructed automatically by processing a huge number of high quality game records. To decide which patterns should be included, the criteria are:

1. How urgent (statistically likely) the move is, e.g. the sooner a move is played on a patterns center point, the higher the likelihood that the pattern will be included in the database.

2. How often a play on the pattern (on its center point) occurs. For quality reasons, exotic patterns are discarded.

Author of MoyoGo writes:

Earlier experiments with Bayesian learning have proved computationally intensive and too fuzzy (we require exact statistical data for each pattern, therefore the algorithm for computing the statistical move likelihood is:

How often the pattern occurred in all games

---------------------------------------------------------

How many turns the average player waited to play there

Given a Baduk position system finds all the patterns that match on some place of the board, i.e. all criteria: stones location, pae status, edge distance, etc. are matched. Then several patterns with highest urgency are selected and given to the user as plausible moves. Because of the relatively large pattern database, and due to the fact that all relevant smaller patterns are included, every Baduk position always contains several to many recognized patterns.

Strong points of explicit pattern system:

1. The system matches and classifies patterns near-instantaneously. On a modern PC, a Baduk position is scanned for matching patterns in less than a millisecond.

2. The system achieves an extraordinary high pro-prediction rate (40% average).

3. The system is a whole-board context aware and often plays like a pro in positions without much tactical complexity.

Weak points:

1. The system is purely static, it cannot read ahead so the more complex and hot a tactical situation is, the worse the system performs.

2. Pattern shapes do not adapt to the Baduk position, they are fixed.

3. The system does not take ladders into account.

Author of MoyoGo also describes future work on MoyoGo pattern system:

The system is in constant development, future work includes:

1. The inclusion of n-th order liberties in the patterns. Order 2 liberties are liberties of liberties, and are a measure for a string of stones to escape enclosure.

2. Using a larger pro games database.

3. Using the rank of the player as a heuristic for the reliability of the statistical move likelihood of the pattern-move.

4. Strong tactical module.

II.2 Finding territory and potential territory

Probably the most well known algorithm for estimating territory and influence is Bouzy's mathematical morphology [Bou03]. It relies on two operations borrowed from the image processing domain: erosion and dilation. The algorithm is very simple yet it is able to quite precisely capture the human notion of territory. The four diagrams above shows state of the algorithm after each of four dilations, while the diagram on the side shows the state after additional thirteen erosions – the approximation of territory. Of course it is purely ``graphical'' and to produce good estimates it needs information about group strength.

Another algorithm for finding the potential territory is presented in [Ste04]. A board is treated as a Markov finite field where the propagation of influence occurs. The main difference from the Bouzy's approach is that the parameters used in the propagation are determined automatically basing on a large number of game records.

The same problem was approached in [Wer04] with the use of neural networks. The resulting algorithm was compared to many methods including the one created by Bouzy. In all the approaches the results were very similar.

II.3 Scoring the final position

A simpler problem than finding territory during a game is to score the final position. Sometimes it may be simple enough to apply exact methods - to prove that the territory is secure. The first such an algorithm was proposed by Benson [Ben76]. It is able to check whether a group is alive unconditionally i.e. whether it will survive even if the defender will always pass.

An extension of it was proposed by Mueller in [Mue97]. His method created static rules that together with search provided a proof in the form of a strategy that guaranteed safety of the territory. He was able to prove the safety of about a quarter of intersections in a final position.

Mueller's work was followed in [Niu04a, Niu04b]. The methods used for recognizing safe territories were extended by search-based techniques including region-merging and a method for efficiently solving weakly dependent regions. This method can prove safe two time more intersections than the previous algorithm.

But still for practical applications a heuristic method is more useful. A good example might be an algorithm by Erik van der Werf [Wer03a]. He used a neural network fed with features of classified groups. His classifier was tested on the same set of 31 positions that was used by Mueller. Only two positions were classified incorrectly while the number of incorrectly scored intersections is less than a half a percent.

II.4 Endgames

Elwyn Berlekamp and David Wolfe [Ber97] successfully applied sophisticated and very elegant Combinatorial Game Theory (CGT) [Ber82] to a (very) late Baduk endgame. CGT evaluates each independent part of the board separately, and then sum the results to evaluate value of a whole board. This is possible by taking into account a possibility of two or more consecutive moves of the same player.

As a simple exercise, a reader may try to guess which move in position shown on diagram, (a) or (b), is better. Intuition suggests that (a) should be better, because the threat to rescue the stones is bigger and will come sooner, but actually (b) is better. If white will play a move (c) then black may play at (b) a mirror white strategy gaining a draw. But if black will answer at (a) than reader may check that white have a forced line to win by one point.

The power of CGT allows for solving problems that even a several Japanese and Chinese 9-dan players were unable to solve.

II.5 Small boards

Few years ago 5x5 Baduk [Wer03c] was solved by a computer for every opening move. It is not a surprise that playing in the centre allows to control the whole board (but it's not trivial either). In contrast 2x2 and 2x3 opening moves result in surprisingly even game with many pitfalls.

A similar analysis was earlier performed and published in a series of articles by Cho Chikun 9-dan. The computed solution showed one important sequence that even Cho missed. The diagrams in the first row show an optimal line of play while the diagrams in the second row show possible spectacular mistakes.

II.6 Life & Death

Life and death is one of the sub-problems where a computer works well. It is one of a few very well defined sub-problems of Baduk. The problem consists of a description of a Baduk position and the question: ``Can these stones live?'' which means: ``Is there a way to save a particular group of stones regardless of an opponent's play?''. A practical question is: ``How to play to save these stones if it is possible?''

Computers work well, when the group in question is completely surrounded and the number of empty intersections (The number of empty intersections usually is an upper bound for the number of legal moves.) is small.

A good example is a program made by Thomas Wolf - GoTools [Wol94, Wol99]. It solves life and death problems with speed equivalent to an amateur high dan player, so programs in this area are much stronger than in general play. Such performance is achieved by a brute-force search aided with a large number of heuristics. GoTools is also able to create Baduk problems. An example is given on diagram.

The weak point of GoTools is that it needs the questioned group to be completely surrounded, and the number of empty intersections not too big, to avoid a combinatorial explosion of possible variants.

Recently, Akihiro Kishimoto [Kis03, Kis05] adopted a different search algorithm - proof number search[All94] to solve a ``one eye'' life and death problems and obtained good results.

A different, more theoretical approach was taken by Howard Landman [Lan96]. He applied Combinatorial Game Theory (CGT) [Ber82] to evaluate the number of eyes the group has in each area. It is natural that group may have one or two eyes; even a half eye is a natural term for humans. Applied CGT may prove that number of eyes in some situations may be equal to 3/4 or 1 1/4. If the sum of such numbers is equal or greater than two, then CGT proves that the group is alive.

All of the mentioned techniques are dynamical and exact. I.e. the algorithms are based on search and their answer is always correct. Another possible approach is a soft one, concentrating rather on the fast finding of good solutions in the majority of cases while allowing few mistakes rather than trying to prove the solution in each problem. Such approach is usually more practical.

Good examples of a soft and static approach on life and death problems are works of Chen [Che99] and Erik van der Werf [Wer03b]. Chen replaces the complex search tree by a set of static heuristics - rules that, when applied to a particular problem, classify each point of the eye-space into one of several categories allowing relatively accurate estimation of a number of true eyes.

The work by Erik is an example of a "fuzzy" approach. His algorithm, given a life and death problem, for each chain in the problem, evaluates values of several easily computable geometric features such as a number of stones, liberties, bents, split points, etc and feeds the results to an artificial neural network to obtain information about the group's state. The network is trained on a large number of examples and is capable of predicting fate of some chains. The results of such a prediction are taken into account in prediction of neighbor chains. Such an approach applied to human game records obtained from Baduk servers classifies correctly 85% - 95% of chains.

II.7 Conclusion

Baduk is a very difficult domain for computers. A various Baduk sub-problems are researched separately with an aim to create a strong program in the future. Currently the most active and promising research directions are Monte-Carlo and large pattern systems. But the domain is very diverse and it is difficult to foreseen directions of further research and results. It is possible that during the next hundred years we will not be able to create a very strong computer player, who will be worthy of a human professional. But it is also possible that there will be a breakthrough in nearest months. This unpredictability renders the computer Baduk a very interesting research domain.

BIBLIOGRAPHY

[All94] Victor L. Allis. Searching for Solutions in Games and Artificial Intelligence. PhD thesis, University of Limburg, 1994.

[Ben76] David B. Benson. Life in the game of Go. Information Sciences, 10:17-29, 1976.

[Ber82] Elwyn Berlekamp, John Conway, and Richard Guy. Winning Ways. Academic Press, 1982.

[Ber97] David Wolfe, Elwyn R. Berlekamp. Mathematical Go : Chilling Gets the Last Point. A K Peters Ltd, 1997.

[Bil02] D. Billings, A. Davidson, J. Schaeffer, and D. Szafron. The challenge of poker. Artificial Intelligence, 134(1):201-240, 2002.

[Boo90] M. Boon. A pattern matcher for Goliath, Computer Go, 13, 1990.

[Bou01] Bruno Bouzy and Tristan Cazenave. Computer Go: an AI oriented survey, 2001. Preprint for article in AI Journal.

[Bou03] Bruno Bouzy. Mathematical morphology applied to computer go. IJPRAI, 17(2), 2003.

[Bou03a] Bruno Bouzy. Associating domain-dependent knowledge and Monte Carlo approaches within a Go program. Information Sciences, 2003.

[Bou03b] Bruno Bouzy and Bernard Helmstetter. Developments on Monte Carlo Go, 2003. Submitted to ACG10.

[Bou04] Bruno Bouzy. Associating shallow and selective global tree search with Monte Carlo for 9x9 Go. In 4rd Computer and Games Conference, Ramat-Gan, 2004.

[Bou05a] Bruno Bouzy and Guillaume Chaslot. Bayesian generation and integration of k-nearest- neighbor patterns for 19x19 Go. In G. Kendall and Simon Lucas, editors, IEEE 2005 Symposium on Computational Intelligence in Games, Colchester, UK, pages 176-181, 2005.

[Bou05b] Bruno Bouzy. Associating domain-dependent knowledge and Monte Carlo approaches within a Go program. Information Sciences, 2005.

[Bru93] Bernd Bruegmann. Monte Carlo Go, 1993.

[Bum05] Daniel Bump, Farneback Gunnar, and Arend Bayer. Gnu go, 2005.

[Caz00] Tristan Cazenave. Abstract proof search, 2000. Submitted paper.

[Caz02] Tristan Cazenave. A generalized threats search algorithm. In Computers and Games 2002, Edmonton, Canada, 2002.

[Caz05] Tristan Cazenave and Bernard Helmstetter. Combining tactical search and monte-carlo in the game of go. In IEEE Symposium on Computational Intelligence and Games, 2005.

[Che99] Zhixing Chen and Ken Chen. Static analysis of life and death in the game of Go. Information Sciences, 121:113-134, 1999.

[Cou06] Rémi Coulom. Efficient selectivity and backup operators in Monte-Carlo tree search. Submitted to CG 2006, 2006.

[Fot92] David Fotland. Many Faces of Go. 1st Cannes/Sophia-Antipolis Go Research Day, Februar 1992.

[Fot93] David Fotland. Knowledge representation in The Many Faces of Go, 1993. Available by Internet.

[Gin99] Matthew Ginsberg. Gib: Steps toward an expert-level bridge-playing program. In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. Information Processing Society of Japan, 1999.

[Gro06a] Frank de Groot, personal communication, 2006.

[Gro06b] MoyoGo, , 2006.

[Kam02] Piotr Kaminski. Las Vegas Go. Available by Internet, 2002.

[Kis03] Akihiro Kishimoto and Martin Mueller. Df-pn in Go: An application to the one-eye problem. In Advances in Computer Games 10, pages 125-141. Kluwer Academic Publishers, 2003.

[Kis05] Akihiro Kishimoto and Martin Mueller. Dynamic Decomposition Search: A Divide and Conquer approach and its application to the one-eye problem in Go. In IEEE Symposium on Computational Intelligence and Games (CIG'05), pages 164-170, 2005.

[Lan96] Howard Landman. Eyespace Values in Go, pages 227-257. Cambridge University Press, 1996.

[Mue97] Martin Mueller. Playing it safe: Recognizing secure territories in computer Go by using static rules and search. In Game Programming Workshop in Japan '97, MATSUBARA, H. (ed.), Computer Shogi Association, Tokyo, Japan, 1997.

[Niu04a] Xiaozhen Niu and Martin Mueller. An improved safety solver for Computer Go. In Computers and Games 2004, Ramat-Gan, Israel, 2004.

[Niu04b] Xiaozhen Niu. Recognizing safe territories and stones in computer Go. Master's thesis, Department of Computing Science, University of Alberta, 2004.

[Rei75a] Walter Reitman, James Kerwin, Robert Nado, and Bruce Wilcox. Goals and plans in a program for playing Go. In ACM Annual Conference, 1975.

[Rei75b] Bruce Wilcox Walter Reitman. Perception and representation of spatial relations in a program for playing Go. In ACM Annual Conference, pages 37-41, 1975.

[She02] B. Sheppard. World-championship-caliber scrabble. Artificial Intelligence, 134(1):241- 275, 2002.

[Ste04] David Stern, Thore Graepel, and David J.C. MacKay. Modelling uncertainty in the game of Go. In Advances in Neural Information Processing Systems 17, 2004.

[Ste05] David Stern, Ralf Herbrich, and Thore Graepel. Bayesian pattern ranking for move prediction in the game of Go. Draft, 2005.

[Sto91] David Stoutamire. Machine Learning, Game Play, and Go. PhD thesis, Case Western Reserve University, , Case Western Reserve University, 1991.

[Tes97] G. J. Tesauro and G. R. Galperin. On-line policy improvement using monte-carlo search. In Advances in Neural Information Processing Systems: Proceedings of the 1996 Conference. Cambridge, MA. MIT Press., 1997.

[Urv02] Tanguy Urvoy. Pattern matching in Go with DFA, 2002.

[Wer02] Erik van der Werf, Jos Uiterwijk, Eric Postma, and Jaap van den Herik. Local move prediction in Go. In 3rd International Conference on Computers and Games, Edmonton, 2002.

[Wer03a] W.H.M. Uiterwijk E.C.D. van der Werf, H.J. van den Herik. Learning to score final positions in the game of Go. In 10th Advances in Computer Games conference, pages 143- 158, 2003.

[Wer03b] M.H.M. Winands E.C.D. van der Werf, H.J. van den Herik, and J.W.H.M. Uiterwijk. Learning to predict life and death from Go game records. In Ken Chen et al., editor, Proceedings of JCIS 2003 7th Joint Conference on Information Sciences, pages 501-504, Research Triangle Park, North Carolina, USA, 2003. JCIS/Association for Intelligent Machinery.

[Wer03c] Erik van der Werf, Jaap van den Herik, and Jos Uiterwijk. Solving Go on small boards. ICGA Journal, 26(2):92-107, 2003.

[Wer04] J. W. H. M. Uiterwijk E.C.D. van der Werf, H.J. van den Herik. Learning to estimate potential territory in the game of Go. In 4th International Conference on Computers and Games (CG'04), 2004.

[Wol94] Thomas Wolf. About computer go and the tsume go program Gotools, 1997. Based on an article from 1st game programming workshop, hakone, Japan, 1994.

[Wol99] Thomas Wolf. Forward pruning and other heuristic search technics in tsume go, 1999.

[Zor71] Albert L. Zobrist. Complex preprocessing for pattern recognition. In ACM annual conference 1971, 1971.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download