Connect Four, Part 2

This blog contains explanation of the paper by Victor Allis called ‘A Knowledge-based Approach of Connect-Four’ This is a 2 part series exploring the paper, and I would suggest going through ‘first part’ if you haven’t already.

🕵️‍♂️ Strategies

A formal definition is given of the nine rules which are used to refute potential threats of the opponent. These can be only applied by the player in control of the Zugzwang. These are always applied in the places opponent has to move.

Claimeven

This makes direct use of the fact that player in control of Zugzwang can get all even unclaimed positions, giving odd positions to the other.

B is in control of Zugzwang here since W doesn’t have any threat. Here, if B were to use claimeven, he could end up getting a draw, since any threat of W will need to have a coin in even row, which will not be possible.

Baseinverse

This is based on the logic that a player cannot play two directly playable moves in one turn. Therefore once the opponent has made the move, controller of Zugzwang can still cover the other position.

Here, if W cannot play in a1 and b1 at the same time. That means if W plays in a1, B plays in b1, and vice versa. Thus the threat is nullified.

Verticle

Similar to Baseinverse, this is based on the fact that a player cannot play two directly playable moves in a single column in one turn. Depending on the opponent, the player controlling the Zugzwang can either play second or first in the column to prevent a verticle 4.

Aftereven

Aftereven uses a special side-effect of the usage of one or more Claimevens. If a group can be completed by the controller of zugzwang, then they can complete the whole board using claim even, and then complete that group:

Here, B can use aftereven to complete the group at either b2 or f2. Here, then B can use claimeven to finally force W to play in either b1 or f1. This is called as aftereven, where you can form a group and win by using claimevens.

Lowinverse

Lowinverse is based on the fact that two odd numbers when summed give an even number. Normally, controller of Zugzwang will play lowest even square of the column containing odd number of empty squares. But when we have two columns (doesn’t have to be consecutive) having odd number of empty squares, this will force the opponent to play first. In such a way controller of zugzwang gets to take the odd square above the opponent.

Highinverse

This is based on the same principle as that of lowinverse:

In lowinverse, we would consider c2, c3, d2, d3 as important. Here we consider c4 and d4 as important too. Highinverse is nothing but a combination of lowinverse and claimeven. What this does is say W plays in c2, then using lowinverse B can get c3. Then B (controller of Zugzwang) convert d3 and d4 into a claimeven, to get d4. In such a way B ends up getting c3 and d4.

Baseclaim

This is a combination of Baseinverse and Claimeven:

Here, W can possibly have 3 threats formed: b1-e1, c1-f1, b1-e4(diagonal). B needs to play in a way to counter this.

• W plays in b1, B plays in e1 and then uses Claimeven at c1-c2 to prevent b1-e4.
• W plays in c1, B plays in e1 and then uses Claimeven at b1-c2 to prevent b1-e4.
• W plays in e1, B plays in c1 and then uses Claimeven at b1-c2 to prevent b1-e4.

In such ways B can nullify all of W‘s threats.

Before

This is a combination of Claimeven and Vertical:

Here b4-e1 is the Before group. Since b4 and e1 are still empty, this means it works for all groups needing both b5 and e2 (b5-e2). Here, before uses the squares b4-b5 and e1-e2. As soon as b4 is played, b5 is played, and same with e1-e2. This will ensure B completing b4-e1 or preventing W‘s b5-e2. In both cases b5-e2 is a useless threat.

It basically means that if there is a before group, the opponent cannot claim all the unclaimed squares in the threat column.

Special Before

We use d2-g2 as the before group. This can contain claim evens at f1-f2 and g1-g2 and vertical at e2-e3. We need to use baseinverse to solve a1-d1, which would give W a possibility of b1-e4. To combat this, we can use claimeven to get e4. This claimeven, however, is conflicting with vertical at e2-e3.

The only reason B needs to play e3 is to prevent d3-g3. So B can play d3 as well. If W were to play at d3 before, then B should immediately get e2 to continue with the Before play. Therefore to play a Special Before, we need a before group (d2-g2) with one of the empty squares as directly playable (e2). Furthermore, we need another playable square (d3).

Combination

⚫⚪ Black and White

Black

We have developed a set of rules which can be used to show that certain potential threats can be refuted. Since some of the rules depend on Zugzwang, it is important that the person who applies them is in control of the Zugzwang.

B is in control of Zugzwang until W creates an odd threat. Till then if B just plays using the strategy. If W were to create a good threat (odd threat), B is no more in control of Zugzwang. Here we observe that no matter what B does from here on out, there generally will not be any set of rules which can refute that threat.

From this we can conclude that we do not need to check who controls the Zugzwang for B before applying the rules. For if B is in control, we can apply the rules, if not, it doesn’t matter what B does.

White

W needs an odd threat to gain control of Zugzwang. Once it has that, he just needs to follow the strategic rules to fill up the rest of the board. If W has more than one odd threat, it can choose from which poison to kill B from.

Victor

A position in which W has to move, can be evaluated as B as controller of Zugzwang, and vice versa. For W as a controller of Zugzwang, evaluation must be done removing the odd column out of viable options. The evaluation begins with finding all possible instances of the 9 strategic rules.

For each position where any rule is applied, it is seen whether it can solve a problem or not. Each application of one of the rules which solve one or more problems is stored. These are called Solutions. This results in a list of solutions, where each solution is stored as a Struct. Struct consists of fields describing the rule, and the positions involved. Furthermore for each solution we have a list of groups solved by that solution.

We also create a map with problem as the key and list of pointer(s) to the solution as the values. After all this, we need to see which solutions can work together and which cannot. To work this out, solutions are seen as nodes of an undirected graph. If two solutions can’t be used simultaneously, they are connected. These connections are stored in an adjacency matrix. To fill it, it is important to know type of solutions and squares involved. Once it is filled, it is a normal square array.

If we see the problems as nodes, too, and we connect a solution and a problem if the solution solves the problem, and no problems are connected, we can solve it as a pure graph problem.

Given are two sets of nodes, S(olutions) and P(roblems). We try to find an allowable (in graph theory: independent) subset C(hosen) of S, with the property that P is contained in B(C) (the set of all neighbours of nodes in C)

It can be solved using a simple backtracking algorithm.:

void FindChosenSet(P, S) {
    if (P == EmptySet) {
        Eureka(); // We have found a subset C
    } else {
        MostDifficultNode = NodeWithLeastNumberOfNeighbours(P);
        for (auto neighbours: MostDifficultNode) {
            FindChosenSet(
            P - { MostDifficultNode },
            S - AllNeighboursOf(ChosenNeighbour)
            );
        }
    }
}

If a set of solutions is found for a given position, these solutions show the plan which has to be followed to play the game until the desired result (win for White, or at least a draw for Black) is reached.

🧠 Food for Thought

Lets assume we have an oracle. This oracle cannot predict who will win, but for any given state of board, give the best possible outcome. Let us assume that we play such that for each state of board, we ask for help from the oracle. Therefore it is a ‘perfect’ game. In such case, if W wins, does that mean W will always win if it were a perfect game?

The thing is, if for B we were to choose that draw is fine, it will not change any result. Since oracle predicts the best move, if the second scenario gives different result, that would mean Oracle could have chosen the best move, but did not. That is contradictory. That means that whoever will win with the help of the Oracle, is always at an advantage.

Another thought to explore is number of legal ways to arrange $N$ coins in board. For now, we take the board to be the standard $7 \times 6$ board.

📝 References

• Resources by Victor Allis
• Alpha Beta Pruning based heuristics
• Principles and Tehniques BY Stanford
• C4 Numbers by oeis org
• Math oriented resources behind Connect-4