Loading...
Please wait, while we are loading the content...
Similar Documents
Combinatorial game theory
| Content Provider | Indraprastha Institute of Information Technology, Delhi |
|---|---|
| Author | Raj, Pranav P |
| Abstract | Combinatorial Game Theory is the theoretical computer science eld which studies two- player sequential games with perfect information. A combinatorial game can be de ned using a set of positions in the game P, the initial position p0 and the move functions M0 and M1, which de nes the moves available for both the players at each position. Impartial games is a subset of combinatorial games in which a move from each position is independent of the player and only depends on the position i.e. M0 and M1 are equivalent. NIM is example of an impartial game. Sprague-Grundy theorem is used to analyze such games. It associates number with each position which determines the presence or absence of a winning strategy from that position. Comparing games can also be used to devise better winning strategies. We study a zero player game called Conway's game of life. In the rst part of the report we explain a new impartial version of the Conway's Game of Life and some properties of this variant. In the end we extend the proof of universality of normal Conway's game of life to answer some complexity related problems. |
| File Format | |
| Language | English |
| Publisher | IIIT Delhi |
| Access Restriction | Authorized |
| Subject Keyword | Combinatorial Game Theory Conway's game of life Impartial Games Theory Turing Machine Universality Complexity Analysis |
| Content Type | Text |
| Educational Degree | Bachelor of Technology (B.Tech.) |
| Resource Type | Thesis |
| Subject | Data processing & computer science |
