Combinatorial Games: Tic-Tac-Toe Theory

Combinatorial Games: Tic-Tac-Toe Theory is a monograph on the mathematics of tic-tac-toe and other positional games, written by József Beck. It was published in 2008 by the Cambridge University Press as volume 114 of their Encyclopedia of Mathematics and its Applications book series ( ISBN978-0-521-46100-9).

Topics

A positional game is a game in which players alternate in taking possession of a given set of elements, with the goal of forming a winning configuration of elements; for instance, in tic-tac-toe and gomoku, the elements are the squares of a grid, and the winning configurations are lines of squares. These examples are symmetric: both players have the same winning configurations. However, positional games also include other possibilities such as the maker-breaker games in which one player (the "maker") tries to form a winning configuration and the other (the "breaker") tries to put off that outcome indefinitely or until the end of the game.^[1] In symmetric positional games one can use a strategy-stealing argument to prove that the first player has an advantage,^[2] but realizing this advantage by a constructive strategy can be very difficult.^[3]

According to the Hales–Jewett theorem, in tic-tac-toe-like games involving forming lines on a grid or higher-dimensional lattice, grids that are small relative to their dimension cannot lead to a drawn game: once the whole grid is partitioned between the two players, one of them will necessarily have a line. One of the main results of the book is that somewhat larger grids lead to a "weak win", a game in which one player can always force the formation of a line (not necessarily before the other player does), but that grid sizes beyond a certain threshold lead to a "strong draw", a game in which both players can prevent the other from forming a line. Moreover, the threshold between a weak win and a strong draw can often be determined precisely. The proof of this result uses a combination of the probabilistic method, to prove the existence of strategies for achieving the desired outcome, and derandomization, to make those strategies explicit.^[4]

이 책은 길이가 긴(732쪽)^[4]으로 49장 4부로 구성되어 있다. 파트 A는 약한 승리(선수가 승리하는 구성의 존재를 강요할 수 있음)와 강한 승리(선수가 승리하기 전에 승리하는 구성이 존재할 수 있음)의 구분을 살펴본다. 그것은 플레이어가 어떤 유한한 포인트 세트의 일치된 복사본을 만들려고 시도하는 비행기의 포인트에 대한 메이커-브레이커 게임의 경우, 메이커는 항상 약한 승리를 거두지만, 그러기 위해서는 때때로 브레이커가 더 일찍 승리 구성을 형성하도록 허용해야 한다는 것을 보여준다. 또한 틱택토(tic-tac-toe)와 같은 대칭 라인 형성 게임의 광범위한 분석을 포함하고 있으며, 희박한 일련의 승리 구성이 메이커-브레이커 게임으로 이어지는 에르드-셀프리지 정리에 대해 논의한다. 이 책의 B부에서는 Erdős-Selfridge의 정리가 증명된 잠재력 기반 방법에 대해 논의하며, 이를 메이커의 승리가 있는 몇 가지 사례를 포함한 추가 사례로 확대한다. 파트 C는 포지셔닝 게임의 결과를 결정하는 더 진보된 기술을 다루며, 한 플레이어가 두 개의 언초센 요소를 선택하고 다른 플레이어가 각 플레이어에 어떤 것을 줄지 선택하는 선택-선택 게임을 포함하여 이러한 유형의 더 복잡한 게임을 소개한다. D부에는 게임의 분해와 램지 이론의 기법을 사용하여 게임에 대한 이론들을 증명하는 내용이 포함되어 있다.^[1] 이 분야의 개방적인 문제들의 모음은 책의 마지막에 제공된다.^[2]

청중 및 접대

이것은 인기 있는 청중보다는 이 지역의 연구자들을 겨냥한 모노그래프다. 리뷰어 윌리엄 가사치는 비록 이 작품이 낮은 수준의 조합과 가능성을 넘어 독자에 대한 배경 지식이 거의 없다고 하지만, "자료는 여전히 어렵다"^[1]고 쓰고 있다. 마찬가지로, 평론가 카일 버크는 "많은 정의와 설명이 어색하게 '수학을 무겁게 한다'고 불평한다. 더 간단한 서술이 충분할 수 있는 고급 수학의 정의되지 않은 용어들이 작은 예에 많이 있다."^[5]

그 책의 많은 부분은 이전에 알려진 것을 단순히 요약하기 보다는 새로운 연구에 관한 것이다.^[4][1] 검토자 알레스 풀트르는 이 책을 "지금까지 문헌에서 불충분하게 제시된 주제 중 가장 철저하고 유용한 취급이며, 그 결과들이 엄청나게 저장되어 있고, 다른 이론들과 연계되어 있으며, 흥미로운 개방형 문제들"이라고 부른다.^[3] Gasarch는 동의한다: "만일 당신이 그것을 통과하면 당신은 많은 수학을 배울 것이다."^[1] 유럽수학회의 필명 평론가는 이 책이 "합성 게임 이론의 발달에 이정표가 될 수 있다"^[2][5]고 덧붙인다.

참조