Penn Arts & Sciences Logo

Friday, April 27, 2012 - 2:00pm

Elwyn Berlekamp

University of California, Berkeley

Location

West Chester University

UNA 158

This talk will review the rudiments of combinatorial game theory [1] as exemplified by a game called Hackenbush. Positions are seen to have values, which are sums of numbers and infinitesimals, such that the winner depends on how the total value compares with zero. We then discuss how refinements of this theory have been applied to the classical Asian board game called Go. The most important tool is the "cooling operator" [2], which maps combinatorial games into other combinatorial games. In the first application, many late stage Go endgame positions [3] are shown to be combinatorial games which, when cooled by 1, often reduce to familiar numbers and infinitesimals. Combinatorial game theory then enables its practitioner to win the endgame by one point. In the second application, Nakamura[4] has shown that liberties can also be viewed as combinatorial games which become familiar numbers and infinitesimals when cooled by 2. In a large class of interesting positions, this approach identifies the move(s), if any, which win the capturing race. Although not prerequisite to this talk, more details can be found in these references: [1] Berlekamp, Conway, and Guy: Winning Ways, Chap 1 [2] Berlekamp, Conway, and Guy: Winning Ways, Chap 6 [3] Berlekamp and Wolfe: Mathematical Go [4] Nakamura, in Games of No Chance, vol 3 Elwyn Berlekamp was an undergraduate at MIT; while there, he was a Putnam Fellow (1961). Professor Berlekamp completed his bachelor´s and master´s degrees in electrical engineering in 1962. Continuing his studies at MIT, he finished his Ph.D. in electrical engineering in 1964; his advisors were Claude Shannon, Robert G. Gallager, Peter Elias and John Wozencraft. Berlekamp taught at the University of California, Berkeley from 1964 until 1966, when he became a researcher at Bell Labs. In 1971, Berlekamp returned to Berkeley where, as of 2010, he is a Professor of the Graduate School. He is a member of the National Academy of Engineering (1977) and the National Academy of Sciences (1999). He was elected a Fellow of the American Academy of Arts and Sciences in 1996. He received in 1991 the IEEE Richard W. Hamming Medal, and in 1998 the Golden Jubilee Award for Technological Innovation from the IEEE Information Theory Society. Berlekamp is one of the inventors of the Welch-Berlekamp and Berlekamp-Massey algorithms, which are used to implement Reed- Solomon error correction. In the mid-1980s, he was president of Cyclotomics, Inc., a corporation that developed error-correcting code technology. With John Horton Conway and Richard K. Guy, he co-authored Winning Ways for your Mathematical Plays, leading to his recognition as one of the founders of combinatorial game theory. He has studied various games, including Fox and Geese and other fox games, dots and boxes, and, especially, Go. With David Wolfe, Berlekamp co-authored the book Mathematical Go, which describes methods for analyzing certain classes of Go endgames.