Interactive · 3 questions
Have you ever been one of those people who ALWAYS loses at card games because almost every time you get a terrible hand, and the one time you DO get a good hand, you make it SOOOO obvious that you can’t get anything good out of it?
If so, then combinatorial games are for you! In these types of games, you know exactly, and nothing less, about the game than your opponent does. There are typically only two players. In each game, players alternate turns.
Because of the nature of “perfect information”, these games have been studied by people. An example of one of these peoples was John Conway, creator of Conway’s Game of Life, among other things.
Which of the following below are well known combinatorial games?
Combinatorial games are games that can be “solved”, theoretically. This means that, in some cases, one player has a strategy that works in their favor. A game is called ultra weak if it is proven that there exists a solution, but does not provide an algorithm. A game is called weak if there exists an algorithm that, at the start, produces either a win or a draw for a certain player. A game is called strong if there exists an algorithm that, from any position, secures a win of a draw for a certain player. We also assume that every player wants to win, and that nobody wants to lose to the other person.
For example, take the following game:
Two players play a game. They are given 7 cubes. On each turn, the player can either remove 1 or 2 cubes. The person who removes the last cube is declared the winner. Which player has a winning strategy?
To start this problem, let’s use small cases.
Case 1: The number of cubes is 1.
In this case, the first player can easily win by taking the one piece.
Case 2: The number of cubes is 2.
In this case, the first player can also easily win by taking the two pieces.
Case 3: The number of cubes is 3.
This one is a little trickier. We’ll take this down with multiple cases. First, consider the case in which Player 1 takes one cube. Then Player 2 can take the rest of the cubes and win. The same goes for the other case, when Player 1 takes two cubes. This shows that for 3 cubes, and with perfect play, Player 2 is the winner.
From here we have all the necessary information to make a conjecture on the outcome of the game.
What do you think a general rule is?
From this, we can tell who wins the game overall game with 7 cubes.
Who wins the game?
This is one of the classic combinatorial game theory problems. It has a nice solution, and it requires an interesting approach. Note that with the given information, you can generalize the game using the information to see that whenever the number of cubes is divisible by 3, Player 2 wins. Otherwise, Player 1 wins.
It has been proved that for finite combinatorial games, ones that have no draws, there is a winning strategy for one player. There are multiple strategies that one can use to solve simple combinatorial games. Tough ones, like chess and checkers, are more difficult. Here is a list of some of the tools that you can use.
Backtracking - Start at the ending position, and work your way to the start. This was the method that we used to solve the Take-Away game above.
Symmetry - To a certain extent, copy your opponent. This can guarantee that you are never left without options in some cases.
Pairs - Some games require the use of a grid of some kind. One example is tic-tac-toe. The strategy is used for games which require a grid, and is used to prevent a victory for one player. Generally, the method creates “tiles” on the grid, such that no matter what, Player 1 will play a tile. Player 2 must then play the opposite tile.
This is only an introduction to combinatorial game theory. There is much more to explore!