Artificial Intelligence for Chain Reaction

Chain Reaction is a Combinatorial Game that deserves to receive more mathematical attention than it does.

Here is my AI for Chain Reaction:https://github.com/Agnishom/ChainReactionAI/

The installation instructions for a regular linux platform is available on the README.md.

You are invited to try it out, and yes, Fork me on GitHub!

If you are interested in how this works, read on.

Rules

I will be describing the rules of the two-player (Red and Green) game but this can be generalized to any number of players.

  1. The gameplay takes place in an m×nm \times n board. The most commonly used size of the board is 9×69 \times 6.
  2. For each cell in the board, we define a critical mass. The critical mass is equal to the number of orthogonally adjacent cells. That would be 4 for usual cells, 3 for cells in the edge and 2 for cells in the corner.
  3. All cells are initially empty. The Red and the Green player takes turns to place "orbs" of their corresponding colors. The Red player can only place an (red) orb in an empty cell or a cell which already contains one or more red orbs. When two or more orbs are placed in the same cell, they stack up.
  4. When a cell is loaded with a number of orbs equal to its critical mass, the stack immediately explodes. As a result of the explosion, to each of the orthogonally adjacent cells, an orb is added and the initial cell looses as many orbs as its critical mass. The explosions might result in overloading of an adjacent cell and the chain reaction of explosion continues until every cell is stable.
  5. When a red cell explodes and there are green cells around, the green cells are converted to red and the other rules of explosions still follow. The same rule is applicable for other colors.
  6. The winner is the one who eliminates every other player's orbs.

Here is a video showing the rules in action. And, here is the implementation of the move making algorithm.

The most interesting thing is how unpredictable the game seems to be in the end, at least when you play it with your human friends. The obvious heuristic that tells us you're better off at the moment by having as many orbs as possible turns out to be very wrong. While it so seems to everyone, that say, red will win, blue suddenly takes over.

Heuristic Strategies

In this section, we develop a way to evaluate the value of a board using heuristics that expert players have gathered through their experience. Like any other complex combinatorial games, the heuristic value is not guaranteed to be an indicative of a dominant strategy but usually it turns out to be so.

We shall call a cell critical if the number of orbs in the cell is equal to one less than its critical mass.

  1. If the board is a won game, the value is 10000.
  2. If the board is a lost game, the value is -10000.
  3. For every orb, for every enemy critical cell surrounding the orb, subtract 5 minus the critical mass of that cell from the value.
  4. In case, the orb has no critical enemy cells in its adjacent cells at all, add 2 to the value if it is an edge cell or 3 if it is a corner cell.
  5. In case, the orb has no critical enemy cells in its adjacent cells at all, add 2 to the value, if the cell is critical.
  6. For every orb of the player's color, add 1 to the value.
  7. For every contiguous blocks of critical cells of the player's color, add twice the number of cells in the block to the score.

The heuristic is implemented here

Minimax

The minimax algorithm is an algorithm which evaluates the value of a position in a combinatorial game by looking down the game tree based on the principle that the enemy aims to minimize the player's score while the player aims to maximize it.

In theory, a minimax algorithm should be able to solve any combinatorial game optimally. However, this can only be done for small games like Tic-Tac-Toe. For larger games, the search space blows up exponentially.

For the 9×69 \times 6 instance of chain reaction, I could only afford looking at the best five positions for three plies within a reasonable time. As far as I understand, this is only slightly better than a human who is able to calculate only one or two plies in the same time.

You can check out my search algorithm here
#CombinatorialGames #WinningStrategies #Logic #ComputerScience #ArtificialIntelligence

Note by Agnishom Chattopadhyay
5 years, 9 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list
  • bulleted
  • list

1. numbered
2. list
  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai−1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 ∑i=13 \sum_{i=1}^3
\sin \theta sin⁡θ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

@bobbym none

Agnishom Chattopadhyay - 5 years, 9 months ago
×

Problem Loading...

Note Loading...

Set Loading...