Accession Number : AD0785175

Title :   Heuristic Analysis of Large Trees as Generated in the Game of Go,

Corporate Author : STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s) : Ryder,Jonathan Leonard

Report Date : DEC 1971

Pagination or Media Count : 307

Abstract : The Japanese game of Go is of interest both as a problem in mathematical representation and as a game which generates a move tree with an extraordinarily high branching factor (100 to 300 branches per ply). The complexity of Go (and the difficulty of Go for human players) is thought to be considerably greater than that of chess. The constraints of being able to play a complete game and of being able to produce a move with a moderate amount of processing time were placed on the solution. The basic approach used was to find methods for isolating and exploring several sorts of relevant subsections of the global game tree. This process depended heavily on the ability to define and manipulate entitles of Go as recursive functions rather than as patterns of stones. A general machine-accessible theory of Go was developed to provide context for program evaluations. A program for playing Go is now available on the Stanford PDP-10 computer. (Modified author abstract)

Descriptors :   *Computer programming, *Game theory, Recursive functions, Strategy, Combinatorial analysis, Algorithms

Subject Categories : Operations Research
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE