The objective of this project is to understand the game Connect 4. In this project, I cover the basics of Connect 4, for example, creating the board, checking the validity of a given board, finding a winning board etc. I also study advanced techniques like generating new and valid Connect 4 boards from a particular board and analyzing the multiway graphs (graphs simulating the game moves) of a smaller variation of the Connect 4 game.
The Basics of Connect 4
The Basics of Connect 4
Connect-4 is a two-player board game played on a 6x7 grid in which players choose either of the colors Red or Yellow. Each player gets 21 tokens of their color which they can drop on the board. The players alternate dropping each of their tokens that falls down to the bottom-most unoccupied cell in the grid. The first player to create a horizontal, vertical or diagonal line consisting of four tokens of their own color is declared the winner.
I represent the Connect-4 board as a list of length 6, where each list denotes a row. Furthermore, each list contains 7 elements, each of which denotes a cell of the board. The 0s on the board denote unoccupied cells, the 1s denote a red token, and the 2s denote a yellow token.
I represent the Connect-4 board as a list of length 6, where each list denotes a row. Furthermore, each list contains 7 elements, each of which denotes a cell of the board. The 0s on the board denote unoccupied cells, the 1s denote a red token, and the 2s denote a yellow token.
Representation of an empty Connect Four board:
In[]:=
StartingPosition = Table[0, 6, 7]
Out[]=
{{0,0,0,0,0,0,0},{0,0,0,0,0,0,0},{0,0,0,0,0,0,0},{0,0,0,0,0,0,0},{0,0,0,0,0,0,0},{0,0,0,0,0,0,0}}
The same board represented as a grid:
In[]:=
BoardGrid[board_] := ArrayPlot[board, ColorRules{0 -> White, 1 -> Red, 2 -> RGBColor[1, 0.9, 0]}, ImageSize 50, Mesh->True]BoardGrid[StartingPosition]
Out[]=
I define the variables Player1 as Red, Player2 as Yellow and a tie (NoResult) as white. Player1 and Player2 are used to mainly depict the moves played by the corresponding player.
The colors as variables:
In[]:=
Player1 = RedPlayer2 = RGBColor[1, 0.9,0]NoResult = White
Out[]=
Out[]=
Out[]=
Now, considering the given board is valid, I want to find the next player's move. An observation used here is that whenever it is the first player's move, the number of red tokens is equal to the number of yellow tokens. If it's the second player's move, then the number of red tokens is one greater than the number of yellow tokens.
Now, considering the given board is valid, I want to find the next player's move. An observation used here is that whenever it is the first player's move, the number of red tokens is equal to the number of yellow tokens. If it's the second player's move, then the number of red tokens is one greater than the number of yellow tokens.
Computing the next player who has to play:
In[]:=
FindNextMove[board_] := (cnt1 = Count[Flatten[board], 1]; cnt2 = Count[Flatten[board], 2]; Which[cnt1 == cnt2, 1, cnt1 == cnt2 + 1, 2])BoardGrid[{{0,0,0,0,0,0,0},{0,0,0,0,0,0,0},{0,0,0,0,0,0,0},{0,1,0,0,2,0,0},{2,1,1,2,2,0,2},{2,1,1,1,2,1,1}}]FindNextMove[{{0,0,0,0,0,0,0},{0,0,0,0,0,0,0},{0,0,0,0,0,0,0},{0,1,0,0,2,0,0},{2,1,1,2,2,0,2},{2,1,1,1,2,1,1}}]
Out[]=
Out[]=
2
Checking the Validity of a Board
Checking the Validity of a Board
Whenever a player drops a token in one of the seven columns in Connect 4, it goes to the bottom-most unoccupied cell. This effectively limits the number of new positions that can be obtained from a board to 7 - one for each column. Hence, we need to ensure that no invalid board is generated. This is how I check for the validity of a board:
◼
Whenever a token is put in a particular column, it occupies the bottom-most unoccupied cell in that column.
Checking that each token occupies the bottom-most available cell in its column:
In[]:=
CheckingAllBottom[Player1_:Player1, Player2_:Player2, NoResult_:NoResult, board_] := Module[{NumberOfRows, NumberOfColumns, IsValid, TransposedBoard},TransposedBoard = Transpose[board]; IsValid = True; {NumberOfRows, NumberOfColumns} = Dimensions[TransposedBoard];Table[Which[Length[Cases[{TransposedBoard[[i]]}, {___, 1, 0, ___}] != 0], IsValid = False, Length[Cases[{TransposedBoard[[i]]}, {___, 2, 0, ___}] != 0], IsValid = False],{i, NumberOfRows}]; IsValid]BoardGrid[{{0,0,0,0,0,0,0},{0,0,0,0,0,0,0},{0,0,0,0,0,0,0},{0,1,2,1,0,0,0},{0,1,2,2,1,0,0},{0,1,2,2,2,1,0}}]CheckingAllBottom[{{0,0,0,0,0,0,0},{0,0,0,0,0,0,0},{0,0,0,0,0,0,0},{0,1,2,1,0,0,0},{0,1,2,2,1,0,0},{0,1,2,2,2,1,0}},Player1, Player2, NoResult]
Out[]=
Out[]=
True
◼
As explained above, whenever it’s the first player’s move, the number of red tokens equals the number of yellow tokens, and whenever it’s the second player’s move, the number of red tokens is one more than the number of yellow tokens. Except these two possibilities, all the other boards generated are invalid.
Checking whether the number of tokens played by both players is valid:
In[]:=
CheckingMoves[board_] := Module[{cnt1, cnt2, IsValid}, cnt1 = Count[Flatten[board], 1]; cnt2 = Count[Flatten[board], 2];IsValid = (cnt1 == cnt2 || cnt1 == cnt2 + 1); IsValid]BoardGrid[{{0,0,0,0,0,0,0},{0,0,0,0,0,0,0},{0,0,0,0,0,0,0},{0,1,2,1,0,0,0},{0,1,2,2,1,0,0},{0,1,2,2,2,1,0}}]CheckingMoves[{{0,0,0,0,0,0,0},{0,0,0,0,0,0,0},{0,0,0,0,0,0,0},{0,1,2,1,0,0,0},{0,1,2,2,1,0,0},{0,1,2,2,2,1,0}}]
Out[]=
Out[]=
True
The CheckingValidity[] function combines both the validation functions:
In[]:=
CheckingValidity[Player1_: Player1, Player2_: Player2, NoResult_: NoResult, board_] := Module[{IsValid},IsValid = CheckingAllBottom[board, Player1, Player2, NoResult] && CheckingMoves[board]; IsValid]BoardGrid[{{0,0,0,0,0,0,0},{0,0,0,0,0,0,0},{0,0,0,0,0,0,0},{0,1,2,1,0,0,0},{0,1,2,2,1,0,0},{0,1,2,2,2,1,0}}]CheckingValidity[{{0,0,0,0,0,0,0},{0,0,0,0,0,0,0},{0,0,0,0,0,0,0},{0,1,2,1,0,0,0},{0,1,2,2,1,0,0},{0,1,2,2,2,1,0}}]
Out[]=
Out[]=
True
Checking for a Winning Position
Checking for a Winning Position
A player wins a game of Connect-4 when he or she gets 4 of his or her tokens lined up consecutively in the same row, column or diagonal. I create three functions, each checking one of the ways to win.
To check for 4 similar colored tokens in a row, I iterate over all the possible cells in which the first token (from the left) can be placed. After that, I check whether the next three tokens are of the same color or not.
Checking whether there are 4 tokens of the same color lined up consecutively in a row:
In[]:=
FourInARow[board_, Player1_: Player1, Player2_: Player2, NoResult_: NoResult] := Module[{NumberOfRows, NumberOfColumns, Winner}, {NumberOfRows, NumberOfColumns} = Dimensions[board]; Winner = NoResult;Table[Which[Take[Part[board, i], {j, j + 3}] === {1, 1, 1, 1}, Winner = Player1,Take[Part[board, i], {j, j + 3}] === {2, 2, 2, 2}, Winner = Player2], {i, 1, NumberOfRows}, {j, 1, NumberOfColumns - 3}]; Winner]BoardGrid[{{0,0,0,0,0,0,0},{0,0,0,0,0,0,0},{0,0,0,0,0,0,0},{0,0,0,0,0,0,0},{0,1,1,1,2,1,1},{2,1,2,2,2,2,1}}]FourInARow[{{0,0,0,0,0,0,0},{0,0,0,0,0,0,0},{0,0,0,0,0,0,0},{0,0,0,0,0,0,0},{0,1,1,1,2,1,1},{2,1,2,2,2,2,1}}]
Out[]=
Out[]=
To check 4 in a column, I transpose the board and iterate over all the possible cells in which the first token (from the left) in the transposed board can be placed. Then I check whether the next three tokens have the same color or not.
Checking whether there are 4 tokens of the same color lined up consecutively in a column:
In[]:=
FourInAColumn[board_, Player1_: Player1, Player2_: Player2, NoResult_: NoResult] := Module[{TransposedBoard, NumberOfRows, NumberOfColumns, Winner}, TransposedBoard = Transpose[board]; {NumberOfRows, NumberOfColumns} = Dimensions[TransposedBoard];Winner = NoResult;Table[Which[Take[Part[TransposedBoard, i], {j, j + 3}] === {1, 1, 1, 1}, Winner = Player1,Take[Part[TransposedBoard, i], {j, j + 3}] === {2, 2, 2, 2}, Winner = Player2], {i, 1, NumberOfRows}, {j, 1, NumberOfColumns - 3}]; Winner]BoardGrid[{{0,0,0,0,0,0,0},{0,0,0,0,0,0,0},{1,0,0,0,0,0,0},{1,0,0,0,0,0,0},{1,0,0,0,0,0,0},{1,0,2,2,2,0,0}}]FourInAColumn[{{0,0,0,0,0,0,0},{0,0,0,0,0,0,0},{1,0,0,0,0,0,0},{1,0,0,0,0,0,0},{1,0,0,0,0,0,0},{1,0,2,2,2,0,0}}]
Out[]=
Out[]=
To check 4 in any left to right diagonal, I consider each diagonal that has greater than or equal to four elements in it. For each diagonal, I check whether four continuous elements in the diagonal have the same token or not. To check the same in right to left diagonals, I reverse the list, because of which they become left to right diagonals. Then I repeat the above process.
Checking whether there are 4 tokens of the same color lined up consecutively in a diagonal:
In[]:=
FourInADiagonal[board_, Player1_: Player1, Player2_: Player2, NoResult_: NoResult] := Module[{DiagonalList, ReverseDiagonalList, NumberOfRows, NumberOfColumns, Winner},{NumberOfRows, NumberOfColumns} = Dimensions[board]; Winner = NoResult;Table[DiagonalList = Diagonal[board, i]; Which[Length[Cases[{DiagonalList}, {___, 1, 1, 1, 1, ___}]] != 0, Winner = Player1, Length[Cases[{DiagonalList}, {___, 2, 2, 2, 2, ___}]] != 0, Winner = Player2], {i, -2, 3}]; Table[ReverseDiagonalList = Diagonal[Reverse[board], i]; Which[Length[Cases[{ReverseDiagonalList}, {___, 1, 1, 1, 1, ___}]]!= 0, Winner = Player1,Length[Cases[{ReverseDiagonalList}, {___, 2, 2, 2 ,2, ___}]]!= 0, Winner = Player2],{i, -2, 3}]; Winner]BoardGrid[{{0,0,0,0,0,0,0},{0,0,0,0,0,0,0},{0,0,0,1,0,0,0},{0,0,1,2,0,0,0},{0,1,2,2,0,0,0},{1,2,2,1,0,0,0}}]FourInADiagonal[{{0,0,0,0,0,0,0},{0,0,0,0,0,0,0},{0,0,0,1,0,0,0},{0,0,0,0,1,0,0},{0,0,0,0,0,1,0},{0,0,0,0,0,0,1}}]
Generating New Positions
Generating New Positions
To generate new positions, I first check whether the current board is valid or not. After this, I check whether the current position is a winning position or not. If it is, then I stop generating new positions since the game has ended. Else, I find the next player to move. Then, for each unoccupied cell, if putting a token in the current cell generates a valid board, I generate that board and use it to generate subsequent boards as well.
Generating new positions with first 2 moves played from the starting position:
Creating Multiway Graphs
Creating Multiway Graphs
Now that the basic elements of the game are done, I create graphs for better visualization of the game. It starts with an empty board and a move is depicted by a line. Thus all the configurations of different boards that can be reached in one move are connected by a line, also known as an edge. These are known as multiway graphs.
First 2 moves from the starting board as a multiway graph:
One can hover over each circle to see the state the current Connect 4 board is in.
First 3 moves from the starting board as a multiway graph:
As you can see the graph becomes very congested for 3 or more moves.
Starting From Random Valid Positions
Starting From Random Valid Positions
Now, suppose you're watching a game of Connect 4 and suddenly one of the players ask you to join in. Here I visualize the multiway graph of the game from a given valid position.
The position of the new board:
Now let us visualise the graph of this board after 2 moves. For better understanding, the red colored circles are the positions in which player 1 wins and the yellow colored circles are the positions in which player 2 wins.
2 moves from the new position:
Smaller Variant
Smaller Variant
To show the whole gameplay of Connect 4 via graphs, I considered a 2x3 grid with the only winning condition being two similar colored tokens in a row.
The TwoInARow[] function checks whether there are similar colored tokens next to each other in a single row and returns the winner if the condition is true. For this, I checked all possible positions of the left token in a row and then checked the cell on its right. If it had a similar colored token, then we found the winner.
The TwoInARow[] function checks whether there are similar colored tokens next to each other in a single row and returns the winner if the condition is true. For this, I checked all possible positions of the left token in a row and then checked the cell on its right. If it had a similar colored token, then we found the winner.
Checking whether there are 2 tokens of the same color lined up consecutively in a row:
The generating function pretty much remains the same, except that the winning conditions have been changed from four in a row, column or diagonal to just two in a row.
Generating new positions for a 2x3 grid:
Now, I update the multiway graph to display 2x3 grids. Just like the last graph, every winning position for player 1 has been depicted by a red-colored node and for player 2 has been depicted by a yellow-colored node.
The whole multiway graph for 2x3 grid:
Future Work
Future Work
It remains to be seen whether a pattern occurs in the multiway graph of the whole simulation of the game in a 6x7 grid. A pattern, if found, could boost the research related to this game. For example, although the 6x7 grid has been solved and proved to be a win for the first player if played with perfect accuracy, the larger variants of the game like the 10x10 grid are still unsolved. If a pattern in the Multiway graph of the 6x7 grid is found and the same pattern could be applied to the 10x10 grid and other variants that have larger boards, solving these Connect 4 variants would be easier because one does not have to compute the whole Multiway graph of the game. This breakthrough would not only help boost the research on this game but also might help the research on other similar games.
References
References