Nowakowski Richard - Games of No Chance.pdf - szachowe poradniki - chesschempion

Games of No Chance

MSRI Publications

Volume 29 , 1996

Preface

Combinatorial Game Theory, as an academic discipline, is still in its infancy.

Many analyses of individual games have appeared in print, starting in 1902 with

C. L. Bouton's analysis of the game of Nim. (For exact references to the works

mentioned here, please see A. Fraenkel's bibliography on pages 493{537 of this

volume.) It is was not until the 1930's that a consistent theory for impartial

games was developed, independently, by R. Sprague and P. M. Grundy, later to

be expanded and expounded upon by R. K. Guy and C. A. B. Smith. (Guy is

still going strong, as evidenced by his energy at this Workshop.) J. H. Conway

then developed the theory of partizan games, which represented a major advance.

Based on this theory, D. Knuth wrote his modern moral tale, Surreal Numbers .

The collaboration of E. R. Berlekamp, J. H. Conway and R. K. Guy gave us

Winning Ways , which \set to music", or at least to \rhyme", the theory so far.

In the process, many more games were discovered and analyzed: but more were

discovered than solved!

This Workshop, held from 11 to 21 July 1994, gave evidence of the growing

interest in combinatorial games on the part of experts from many elds: math-

ematicians, computer scientists, researchers in articial intelligence, economists,

and other social scientists. Players, some of whom make their living from games,

also attended. Visitors such as D. Knuth and H. Wilf dropped in for a few

hours or days and gave impromptu lectures. There was much cross-fertilization

of ideas, as could be expected from a meeting of people from such varied back-

grounds. One major paper by A. Fraenkel (pages 417{431) was conceived and

essentially written during the Workshop, being inspired by V. Pless's talk.

But the Workshop was not all seminars. There were books, games and puz-

zles on display. Two ocial tournaments, Dots-and-Boxes and Domineering,

attracted a lot of participants, and carried $500 rst prizes (funded by E. R. B.)

The nal matches were shown over closed-circuit TV, so that the spectators

could have a running commentary! (See pages 79{89.) Neither game is com-

pletely solved: Dots-and-Boxes is played by many school children, yet still holds

mysteries for adults.

The articles in this volume are divided into four groups. Part I is introductory.

Part II contains papers on some of the \classical" games, such as chess and

xii

PREFACE

Go. Part III studies many other games, of greatly varying degrees of diculty.

Part IV contains articles that push the traditional theory in new directions:

for example, by considering games more general than the strict denition of

combinatorial games allows (see pages 1 and 363). The book closes with a list

of unsolved problems by R. K. Guy, and a Master Bibliography by A. Fraenkel.

The increasing role of computers can be witnessed throughout, in areas ranging

from the solution of particular games to the use of the computer in teaching

humans.

Many thanks must go the sta of MSRI, who helped make the Workshop a

success. The facilities were wonderful. Thanks are due also to the Workshop

chairs, E. R. Berlekamp and R. K. Guy. Together with the rest of the orga-

nizing committee (J. H. Conway, N. D. Elkies, A. S. Fraenkel, J. G. Propp, K.

Thompson, and myself), they put together a wonderful and rich program.

In the preparation of this book, we are especially grateful to Silvio Levy,

who essentially rewrote two of the articles, edited all the others, found good

placements for the more than 200 gures, redrew some of them, and arranged

the typesetting.

Richard J. Nowakowski

All Games Bright and Beautiful

What is a combinatorial game? The usual denition is a game in which

(i) there are two players moving alternately;

(ii) there are no chance devices and both players have perfect information;

(iii) the rules are such that the game must eventually end; and

(iv) there are no draws, and the winner is determined by who moves last.

In this section, two master expositors lead us through many examples of such

games, and introduce the theory that has been developed to deal with them

(pages 13{78). As an appetizer, you may prefer to read rst J. H. Conway's

charming study (pages 3{12) of a game that does not satisfy this denition,

because it may well be endless. Or, if you already know the basic theory and

are dying for action, turn to the reports of the Workshop tournament nals, on

pages 79{89; or download the Gamesman's Toolkit, described on pages 93{98.

Have fun!

Strides on Classical Ground

The origins of chess and related games are lost in time; yet, in spite of hundreds of

years of analysis, they remain as interesting as ever, because of their fantastically

large conguration space. The articles presented here are steps in the continuing

endeavor to master these games, an endeavor in which the computer nowadays is

often a valuable tool. In fact, the \simpler" board game Nine Men's Morris has

succumbed to computer analysis, as reported by R. Gasser. Checkers may well

be on its way: J. Schaeer tells of the development of the program Chinook, and

pays a tribute to the extraordinary (human!) player M. Tinsley. N. Elkies and

L. Stiller write articles about chess, computerless in one case and computer-heavy

in the other. Shogi, also called Japanese chess, is Y. Kawano's subject.

The last four articles of this section deal with Go, a game that has come

under intense scrutiny recently. Although it is a territorial game and not, strictly

speaking, a combinatorial game according to the denition on page 1, the board

breaks up toward the end into a sum of smaller independent games, a situation

that the theory of combinatorial games handles well. Other aspects of Go, such

as ko, require extensions of the traditional theory, as explained in two of these

articles.

Taming the Menagerie

This section collects seven analyses of \simple" games in their dizzying variety:

from the hitherto ignored sowing games (where counters are distributed from one

pile to others, without ever being removed from the game) to take-away games

(where there is only one pile, but the rule specifying how many counters can

be removed may be endishly complicated). Not surprisingly, complete analyses

are hard to come by, but several interesting general results are proved. There

is also a description of a computer interface for Domineering, that archetype of

partizan board games, amazing in its economy and elegance.

Nowakowski Richard - Games of No Chance.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: