Combinatorial game theory
There have been 1 completed talk and 1 topic suggestion tagged with combinatorial game theory.
Related Tags
Completed Talks
Game Theory (Part 2): Extensive Form Finite and Infinite Games
Delivered by Koosha Totonchi on Friday January 20, 2017
An extensive form game, unlike a regular one-shot-game, has the element of sequential or repeated movement. Chess for example, is an extensive form game. However, we will see that our mathematical definition of “game” will be much broader, so models we construct can be applied to problems in economics, computer science, and engineering—not just chess.
We will explore what it means to “solve” a game where players make back to back moves. We will also go over games where players pick their moves at the same time but play over and over. There will be a review of basic definitions from Game Theory Part 1, and we will introduce some new terms which will help us with extensive forms.
At the end, we can hopefully look at some interesting applications.
Note: this builds on the first Game Theory talk given in Fall 2016. If you need to review important concepts or you couldn’t attend, a webpage with definitions and basic information is available here. We’ll do a brief review so don’t worry too much! If you didn’t come to the first session, you should be able to understand everything here regardless.
Talk Suggestions
The Angel Problem
A game is played by two players called the angel and the devil. It is played on an infinite chessboard (or equivalently the points of a 2D lattice). The angel has a power k (a natural number 1 or higher), specified before the game starts. The board starts empty with the angel at the origin. On each turn, the angel jumps to a different empty square which could be reached by at most k moves of a chess king, i.e. the distance from the starting square is at most k in the infinity norm. The devil, on its turn, may add a block on any single square not containing the angel. The angel may leap over blocked squares, but cannot land on them. The devil wins if the angel is unable to move. The angel wins by surviving indefinitely.
The angel problem is: can an angel with high enough power win?
Required Background: Basic analysis at the level of 147 and algebra at the level of 145.
Possible reference materials for this topic include
Quick links: Google search, arXiv.org search, propose to present a talk
combinatorial game theory combinatorics game theory research problem