Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Combinatorial Games: Selected Bibliography with a Succinct Gourmet Introduction. | Combinatorial Games Selected Bibliography with a Succinct Gourmet Introduction Aviezri S. Fraenkel Department of Applied Mathematics and Computer Science Weizmann Institute of Science Rehovot 76100 Israel fraenkel@ http .il -fraenkel 1 What are Combinatorial Games Roughly speaking the family of combinatorial games consists of two-player games with perfect information no hidden information as in some card games no chance moves no dice and outcome restricted to lose win tie tie and draw draw for the two players who move alternately. Tie is an end position such as in tic-tac-toe where no player wins whereas draw is a dynamic tie any position from which a player has a nonlosing move but cannot force a win. Both the easy game of Nim and the seemingly difficult chess are examples of combinatorial games. And so is go. The shorter terminology game games is used below to designate combinatorial games. 2 Why are Games Intriguing and Tempting Amusing oneself with games may sound like a frivolous occupation. But the fact is that the bulk of interesting and natural mathematical problems that are hardest in complexity classes beyond NP such as Pspace Exptime and Expspace are two-player games occasionally even one-player games puzzles or even zero-player games Conway s Life . Some of the reasons for the high complexity of two-player games are outlined in the next section. Before that we note that in addition to a natural appeal of the subject there are applications or connections to various areas including complexity logic graph and matroid theory networks error-correcting codes surreal numbers on-line algorithms biology and analysis and design of mathematical and commercial games THE ELECTRONIC JOURNAL OF COMBINATORICS 2009 DS2 1 But when the chips are down it is this natural appeal that lures both amateurs and professionals to become addicted to the subject. What is the essence of this appeal Perhaps the urge to play games is rooted .
