Some of the following might seem trivial, but it wasn’t to me, so I wanted to share.
I’m making a variant of the Connect Four game using vanilla Javascript called, Connect N. It is so called because it’s an implementation where the players can select what size the win condition of connected pieces will be for their game between 3 and 6.
I was inspired to create this game after I made a simple Tic-Tac-Toe implementation and wondered what it would be like with a board size larger than 3x3 - it’s terrible by the way.
Anywho, this post will be primarily about how I solved the arguably most important function in the game: the checkWin function.
Solution Attempt 1
Initially, since I had just finished making Tic-Tac-Toe, I thought of hard-coding an array of possible winning game states (which themselves are arrays) and then simply checking whether any one of those corresponds to the actual game state. You imagine the game board as a single 1-indexed array where the index of each element is either a 0 (no piece) or 1 or 2 (player 1 or 2 piece).
This is an O(n) solution for every time the checkWin function is run. It’s quite good and is in fact how most people solve this function for Connect 4 online.
However, writing out the possible winning states for each board size would have been incredibly tedious.
Solution Attempt 2
The idea was to perform a kind of graph search where each node corresponds to a game cell. We would expand outwards in all directions, track the greatest count of connected pieces, and mark a node as having been visited (so that we don’t perform the search from that same cell later if it didn’t lead to a win). Then, if we reach the win condition, we return true.
Since I never coded this, I’m not sure of its time complexity, but I suspect it’d be O(n) or O(log(n)). This is great, of course, but the thought of coding this up seemed a bit daunting.
Solution Attempt 3 & 4
About here is where I sought the assistance of ChatGPT. Asking it to provide a solution first resulted in a brute-force approach where you’d perform 4 searches for every move: horizontal, vertical, diagonal left-right, diagonal right-left. To be honest, with how small the game state can ever become, even with win conditions of 6 connected pieces, this would run just fine. However, the time complexity is not great. I want to say it’s O(n*k), where n is the length of each row and k is the height of each column.
While I still had the chat window open, I wondered if creating a function that could generate the map for each win condition, instead of hard-coding it, would work. In theory, this is an O(n) solution, but if you account for the generation of such a map, then the solution technically becomes O(n^2).
Final Solution
Somewhere between ChatGPT and searching for other people’s solutions, I had an insight that the last piece played in Connect N is the winning piece. No piece placed before it can cause a win or else it would have already. This insight made me realize that the entire board does not need to be searched for a win after the placement of every piece. You can simply expand outwards, both ways, in all 4 directions from the last placed piece, and if you reach the appropriate count of connected same player pieces, you return true. Eureka!
The time complexity of this solution seems like O(n), but you’re technically bounded by the maximum search range which would be: win condition * 4 - 1. So it’s technically O(1) because it’s a constant search range or less. At least, I think that’s the case.
In any case, this is the solution I coded into my game, and it works great! It is by far the simplest to reason about and the fastest. In addition to that, I made a very minor improvement where the checkWin function is only run for every move played after the minimum number of moves has been played where a win could occur (2 * win condition - 1).