Joseki search, parallel computation and computer Go: A new approach to the Joseki problems.
Item
-
Title
-
Joseki search, parallel computation and computer Go: A new approach to the Joseki problems.
-
Identifier
-
AAI9315503
-
identifier
-
9315503
-
Creator
-
Shyu, Weng-Yu.
-
Contributor
-
Adviser: Michael Anshel
-
Date
-
1993
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Computer Science | Artificial Intelligence
-
Abstract
-
Now that startlingly successful computer chess programs have been developed, a similarly advanced Go program is the next logical goal for the AI game-modeling community. A strong Go program was an original goal of the Japanese Fifth Generation project, but it was later dropped. To date, the best Go programs are still at the beginner level. The primary reason for this is that the game of Go has a much larger number of legal moves than does chess and it is also much harder to evaluate the strength of positions with heuristics. Furthermore, since most Go programs run on a personal computer, they lack necessary computational resources. Because the game tree generated by a Go game is so large, an exhaustive search is not possible with current technology. Adding more computational resources to current programs may enhance the abilities of these programs. Advances in the hardware circuits and the algorithms used to play Go--as we introduce here--make a far greater difference. In this thesis, we develop a system to handle the Go opening game. Because of the multiplicity of choices, this requires a sophisticated searching method and much computational power. First, a pattern recognition program extracts the book knowledge called 'joseki' from a joseki dictionary. Second, a tree construction program compiles the knowledge into a tree. Third, an algorithm is used to match the pattern in a joseki with the pattern on the game board. Fourth, an alpha-beta search and a static evaluation select the best joseki for the next move. Some parallel evaluation algorithms under hypercube machines are also discussed. Finally, logic circuits are designed to implement some of the critical functions in the algorithm and their simulations are shown. These circuits dramatically improve the speed of the algorithm. They can also be applied to the middle game and the end game of a Go program.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
