学 术 报 告
报告人： Prof. Elwyn Berlekamp
(University of California at Berkeley)
题 目： COMBINATORIAL GAMES
报告人简介：Elwyn Berlekamp 教授，美国科学院院士、美国工程院院士，美国加州大学伯克利分校数学系教授，国际著名的从事信息论、算法理论、博弈论、应用分析学、金融工程等领域的顶尖学者。
Elwyn Berlekamp 教授师从信息论之父C. E. Shannon。先后在UC Berkeley电子工程学院、贝尔实验室、UC Berkeley计算机科学系、数学系等任教。Elwyn Berlekamp 教授研究兴趣广泛，著作丰富，著有编码理论、博弈论等领域的专著和编著10本，论文多篇；拥有全美专利12项。其理论研究和实际应用曾多次获奖。
很高兴Elwyn Berlekamp教授此次能接受我系的邀请作短期访问，并给出系列学术报告，欢迎广大老师和学生积极参加。
（其个人信息参见//math.berkeley.edu/`berlek/，本次报告摘要附后）
地 点： 理科大楼数学系 A1510
时 间：
报告1：2005年8月29日 下午 3:00-4:00
报告2：2005年8月31日 下午 3:00-4:00
报告3：2005年9月 1 日 下午 3:00-4:00
数学系
2005-8-23
Abstract for Talks at Shanghai
August 29 – September 2, 2005
COMBINATORIAL GAMES
by Prof. Elwyn Berlekamp
University of California at Berkeley
Combinatorial game theory is concerned with two-person perfect-information games, especially those classes of positions for which winning strategies can be stated explicitly, or at least proved to exist. The powerful mathematical methods (often requiring only paper and pencil, no computers) are most successful when applied to games whose positions tend to decompose into "sums". The many examples of such games include Nim, Dots and Boxes, Hackenbush (best played with colored chalk and erasures), Domineering (played with dominoes on a checkerboard), Konane (popular in ancient Hawaii), Amazons (invented less than fifteen years ago, but which has attracted a substantial following on the Internet), and Go (the classical Asian board game). Decomposition and modularity are crucial issues in a wide variety of disciplines. Combinatorial game theory offers a fascinating domain in which to study them.
The first talk will provide an introduction to how such studies apply to the game of Hackenbush.
The second talk will outline the relationships between combinatorial game theory and some other areas of mathematics and/or computer science: logic, set theory, artificial intelligence, coding theory, complexity theory, statistical game theory, linear programming. It will also discuss the figure above, which shows interesting problems in Go, Domineering, checkers, and chess. In Domineering, white must play a gray domino onto an empty pair of horizontally adjacent white squares; black must play onto an empty pair of vertically adjacent black squares. We show how to solve each of these four problems, as well as a fifth problem in which all of these four games are played concurrently.
A third talk will discuss applications of combinatorial game theory to Go.
