Skip to main content

Game Theory

This page provides links to solutions that use the Game Theory.

Overview​

Game theory is a mathematical discipline that models conflicting behaviors. Here are some of the games

Tic Tac Toe​

  • Players makes move alternatively
  • On a player's turn, they can mark a cell
  • The player who marks rows, columns, or diagonals is the winner

Domineering​

  • Players makes moves alternatively
  • Player1 chooses two consecutive cells horizontally
  • Player2 chooses two consecutive cells vertically
  • The Player who runs out of moves loses
domineering.svg

Chomp​

  • Players makes moves alternatively
  • On a player's turn, they choose one of the remaining chocolate bars to eat
  • When a player eats a chocolate bar, they also remove all chocolate bars that are directly below and to the right of the eaten chocolate bar
  • The player who eats the last remaining chocolate bar (the one at the top-left corner) loses the game
Chomp_game.png

Hex​

  • Players makes moves alternatively
  • On a player's turn, they place a stone of their color on an empty hexagon, aiming to create a path from one side of the board to the opposite side, while also blocking the path of the opposing player
  • The game ends when one player successfully creates a connected path of their colored hexes from one of their sides to the opposite side
hex_board.svg

N and P positions​

There are 2121 sticks in total, and two players take turns picking 11, 22, or 33 sticks during their turn. The player who takes the last stick wins the game. Can you determine which player has a winning strategy?

Theorem​

Suppose we start with N\text{N} sticks, then the first player has a winning strategy.

  • If N\text{N} is not a multiple of 44.
  • If N\text{N} is a multiple of 44, then player 22 wins.

Proof​

It is explained by principle of induction

Todo​

https://www.youtube.com/watch?v=5jBV5zmjT6g&list=PLOzRYVm0a65fY-Vh8Caiv3wAYmDd7SnrN

How to Spot These Problems​

You can identify game theory problems if the problem requires you to:

  • Game theory problems involve situations where individuals or groups (players) must make decisions that affect each other’s outcomes.

Leetcode Problem Set​