Icamp 2013GAME THEORY SUMMER RESEARCH PROJECTS This Research Project Will Combine Computer

iCAMP 2013GAME THEORY SUMMER RESEARCH PROJECTS
This research project will combine computer adaptive learning and mathematical game theory tools to answer open research questions about simple combinatorial games. Each student will work in pairs on one of the game research topics below. All students will meet certain benchmarks during their research development process.
Week 1- Students will play their game a large number of times and develop notation for recording the game play and results. Students will write at least 3 conjectures or questions for investigation regarding the game. Students will begin working on a game simulator program.
Week 2- Students will create a game simulator which can play human vs. human and human vs. random computer. Students will refine their game notation in order to aide in the development of this program. Students will perform an extensive literature search to gather previous relevant work on their game or related games.
Week 3- Students will work any combinatorial questions related to their game including the number of game states and number of possible strategies for each player (some will require approximations). Students will continue to read through and work through the details of any relevant research articles and write a one page synopsis of the 1-2 key related works. Students will begin development on a computer vs. computer adaptive learning program for their game.
Week 4- Students will run extensive trials with their adaptive learning programs. Data will be organized and sorted to begin answering the posed research questions.
Week 5- Students will begin to work on mathematical analyses related to potential conjectures coming out of the adaptive learning program analysis. Students will continue to refine their learning program and run new trials based on the previous outcomes.
Weeks 6-7 Students will continue working on answering their research questions using a combination of computing and analytical tools appropriate to their individual project. Students will being preparing appropriate graphics for presentation of the project results.
Week 8- Students will prepare a poster, paper and presentation on their key research findings.

PROJECT 1:

Moebius, when played on 18 coins has a remarkable pattern. Is there any trace of pattern for larger numbers of coins? Can any estimate be made for the rate of growth of the nim-values? [See Coin-turning games in WW, 432{435; and Vera Pless's lecture and the Impartial Games lecture in PSAM 43.Moebius is played with a row of coins. A move turns 1, 2, 3, 4 or 5 coins, of which the rightmost must go from heads to tails (to make sure the game satisfies the Ending Condition). The winner is the player who makes all coins tails.]Mogul has an even more striking pattern when played on 24 coins, which has some echoes when played on 40, 56 or 64 coins. Thereafter, is there complete chaos?

PROJECT 2: The game Pennywise (or Fight) was developed in 1995 and is a very simple game. Players start with a set of coins such as 4 pennies, 3 nickels, 2 dimes, and a quarter. They take turns playing coins into the center, and taking back as much as they can, up to 1 penny less than what they put in. The goal is to run your opponent out of coins. For various combinations of starting amounts and denominations, you will investigate if this game is fair or unfair and you will find the winning or best strategies for this game.

PROJECT 3:

Welter's Game on an arbitrary digraph. Place a number of monochromatic tokens on distinct vertices of a directed acyclic graph. A token may be moved to any unoccupied immediate follower. Last player wins. Make a dictionary of P-positions and formulate a winning strategy for other positions. See Kahane and Fraenkel [1987] and Kahane and Ryba [2001].

PROJECT 4:

Subtraction games are known to be periodic. Investigate the relationship between the subtraction set and the length and structure of the period. The same question can be asked about partizan subtraction games, in which each player is assigned an individual subtraction set. See Fraenkel and Kotzig [1987]. See also Subtraction Games in WW, 83{86, 487{498 and in the Impartial Games article in GONC. A move in the game S(s1; s2; s3; : : :) is to take a number of beans from a heap, provided that number is a member of the subtraction set, fs1; s2; s3; : : :g. Analysis of such a game and of many other heap games is conveniently recorded by a nim-sequence, n0n1n2n3 : : : ; meaning that the nim-value of a heap of h beans is nh, h = 0, 1, 2, . . . , i.e., that the value of a heap of h beans in this particular game is the nimber _nh. To avoid having to print stars, we say that the nim-value of a position is n, meaning that its value is the nimber _n. For examples see Table 2 in x 4 on p. 67 of the Impartial Games paper in GONC. In subtraction games the nim-values 0 and 1 are remarkably related by Ferguson's Pairing Property [Ferguson [1974]; WW, 86, 422]: if s1 is the least member of the subtraction-set, then G(n) = 1 just if G(n - s1) = 0: Here and later “G(n) = v" means that the nim-value of a heap of n beans is v. It would now seem feasible to give the complete analysis for games whose subtraction sets have just three members, but the detail has so far eluded those who have looked at the problem.

PROJECT 5:
Subset Take-away. Given a finite set, players alternately choose proper subsets subject to the rule that once a subset has been chosen, none of its subsets may be chosen subsequently by either player. Last player wins. It has been shown that this game is a second player win for sets of less than six elements. Extend this analysis and find winning strategies for various board sizes.

PROJECT 6:

Bogart(Crash) is a quick push-your-luck dice game. Each turn, the acting player places one chip from the bank into the pot and rolls one die. If the roll is a one (the player 'aces out'), the turn is over. Otherwise, the player take the pot. Alternatively, the player may add two chips to the pot and roll two dice. If either roll is an ace, the turn is over. This continues until the player aces out, takes the pot, or rolls five dice without acing out - which is an instant win. If no player scores an instant win, the first player to collect thirty chips wins. Analyze best strategies for this game.

PROJECT 7:

Consider taking two or more well-studied combinatorial games for which complete information about winning player and the winning strategy is known. Suppose now two players are playing these games simultaneously such that on a given turn the player can make a legitimate move on any one of the game boards. If one of the game finishes, the winner is noted and play continues in the other games. The winner is the person who wins the most of the games being played. For example, consider playing a game of Nim with piles with 3, 4, and 5 objects, a game of 7 by 7 hex and a game of tic-tac-toe simultaneously. Which player has the winning strategy? Can you come up with a general theory for combinations of games?

PROJECT 8:

There are various ways of playing two-dimensional Nim. One formis discussed on p. 313 of WW. Another is proposed by Berman, Fraenkel andKahane in Problem 41, Discrete Math., 45 (1983) 137{138. Start with a rectangulararray of heaps of beans. At each move a row or column is selected and apositive number of beans is taken from some of the heaps in that row or column;see Fremlin [1973]. Ferguson's [2001] variant has the move as choosing a numberand subtracting that number from all members of a row or column. He finds theoutcomes for 2_2 matrices in both the impartial and partizan versions. Anothervariant is where beans may be taken only from contiguous heaps. Other variantsare played on triangular or hexagonal boards; a special case of this last is PietHein's Nimbi, solved by Fraenkel and Herda [1980].

PROJECT 9:

The game Aggression is a Risk-like game in which players take turns drawing regions then placing armies. Conquering then takes place by selecting neighboring regions to take over. The winner is the one with the largest number of occupied regions at the end of the game. Determine which player has the winning strategy and what that winning strategy is.

PROJECT 10:

Black Box is a game in which the player tries to figure out the location of hidden objects by making guesses with feedback (much like Mastermind or Battleship). The game was developed by Godfrey Hounsfield, the inventor of the CAT scan. Determine the minimum number of guesses needed to solve all boards and develop an optimal guessing strategy.

PROJECT 11:

Take-back-toe is a sowing game with a random element. On a 3x4 board, players will take turns moving chips around. The board starts with a stack of 10 chips on each spacein the center row. On each turn, you roll a 6-sided die, and then move that number of chips from one space to an adjacent space (adjacency is orthogonal, not diagonal). To win, you must be the first player to have three stacks of the same size in your home row (the row closest to you). You can't move fewer chips than the number you roll, so it's theoretically possible that you will be forced to pass. Also, you can't undo your opponent's most recent move. Find the winning strategy for this game.

PROJECT 12:

Analyze the Hub and Spoke version of Nim. (First you will want to look at Burning-the-Candle-at-Both-Ends-

Nim played with a row of heaps. A move may only be madein the leftmost or in the rightmost heap. When a heap becomes empty, then itsneighbor becomes the end heap.Albert and Nowakowski [2001] have solved the impartial and partizan versions.) There are variations of the Hub and Spoke game:

(a) beans may be taken only from a heap at the end of a spoke;

(b) beans may also be taken from the hub;

(c) beans may be taken from the hub only when all the heaps in a spoke areexhausted;

(d) beans may be taken from the hub only when just one spoke remains;

(e) in versions (b), (c) and (d), when the hub is exhausted, beans may betaken from a heap at either end of any remaining spoke; i.e. the game becomesthe sum of a number of games of Burning-the-Candle-at-Both-Ends.

PROJECT 13:

Consider a game in which “rock”, “paper” and “scissor” tokens are placed on opposing sides of a 4 by 3 hex board. Tokens can be moved to any adjacent hex. The usual rules of RPS applies to conquering tokens of the opponent. The first player to advance to the other side of the board or to capture all the opponents pieces wins the game. Analyze this game and find a winning strategy. Generalize to larger boards and larger numbers of tokens. Full game involves Rock, paper, scissors, fire, and water.

PROJECT 14:

3D- Chomp is the basic chomp game played on a 3 dimensional block. Determine N and P positions for this game.

PROJECT 15:

Use quantum computing algorithms to investigate simple non-cooperative games such as chicken and hawk-dove. Find the optimal mixed strategy for the game when using Grover’s algorithm. Some recent literature explores the Prisoner’s dilemma game, but the techniques have yet to be applied to other games, particularly iterated games.

PROJECT 16:

The tumor cells can come in different phenotypes which in turn gain different advantage under various metabolic conditions. Basanta et al. 2008 (Evolutionary game theory elucidates the role of glycolysis in glioma progression and invasion) describe three different phenotypes: AG (autonomous growth), GLY (anaerobic glycolysis) and INV (invasive) and study an evolutionary game between those phenotypes. The game can be described as generalized Rock-Paper-Scissors game and authors’ main objective was to identify conditions for which the INV phenotype appears (as in those cases, the tumor spreads). As part of this proposed project, the students will a) completely analyze the above game with 3 phenotypes, and then build on this work to b) incorporate more phenotypes into the game and c) incorporate spatial aspects of the tumors that have been neglected in previous models. The main objective will stay the same as in the original – identify conditions that allow (or prevent) INV phenotype to appear in order to help device tumor treatment strategies.

PROJECT 17:

Asian carps were imported from China in the 1970s to help clean commercial ponds. However, they subsequently migrated from ponds into the Mississippi, where they quickly reached high population density. They are considered invasive species, highly detrimental to the ecological balance, as they threaten the native fish population, eating up the algae and other organisms essential for the survival of the native fish. The Asian carp now threatens the Great Lakes. In July 2012 Congress enacted the "Stop Invasive Species Act", which requires the U.S. Corp of Engineers to implement measures, which will prevent Asian Carp from invading the Great Lakes from the Mississippi through the Chicago area canal system. The goal of this project is to gain a better understanding of the interaction between native species and Asian carp. Students will develop and analyze gametheoretical models related to the Hawk-Dove-Retaliator game to study the Mississippi invasion of the Asian Carp and its competition with native fish. Specifically, students will study the speed of the invasion and how it depends on various parameters of the game; with the aim to identify values that slow down (or even stop) the invasion. With the help of computer simulations, they will also study how the spatial structure of the river (or the canals) affects the invasion process.