# Connect-Five

#### Pick who goes first!

This project is an adaptation of a lab assignment from one of my Java programming classes. I converted the code from Java to JavaScript, and used Flexbox and css Grids to generate the board, the pieces, and other visual components.

The board consists of a 7×7 grid, and the goal is to get 5 in a row before the computer does. The computer uses a MinMax algorithm to determine the move that will give it the best possible score after checking the board recursively for several iterations.

Unfortunately, because the min-max algorithm recursively iterates through possible moves, there is a limit to how much processing the computer can do before the browser either crashes or stops processing because of a memory limit. Or, the computer moves so slowly because it counts too many options that gameplay isn’t very fun.

A better implementation would be to use a Monte Carlo tree search algorithm to traverse possible board configurations and determine the best outcome there, but that’s a project for another time.

## Computer Strategy

The first thing the computer does is determine it’s opening strategy: build pieces up, or spread pieces out. It’s a simple true/false randomizer (though, not truly random), and if the strategy is to build up, the computer’s first move is going to be weighted to be one of the centermost columns.

``````let up = Math.random() > 0.5;
let bestMove = 0;
if(up === true) {
bestMove = Math.floor(Math.random() * Grid.length / 2) + Math.floor(Grid.length / 4);
} else {
bestMove = Math.floor(Math.random() * Grid.length);
}``````

After calculating the best beginning move for the computer, the computer will follow the up or out strategy for the first four moves, and then the min-max algorithm takes effect.

``````if (player === 'o') {
if (isFirstMove === 3) {
bestMove = bestComputerMove(Grid, 6, bestMove);
} else {
if(!up) {
bestMove = (bestMove + 1) % Grid.length;
}
isFirstMove++;
}
/* ... */
}``````

The strategy is far from fool-proof, and if the computer’s strategy is to spread out, it’s quite easy to block groups of the computer’s pieces in the early game. The idea isn’t for the computer to win its first 5 moves. The idea is instead for the computer to have varied opening strategies so that playing the game isn’t boring or predictable.

Once the computer has completed their 4th move (if it goes first) or its 3rd move (if you go first), the min-max algorithm goes into effect.

The min-max algorithm takes the current board, and iterates through each column in the board, placing a virtual piece and calculating whether or not that piece either blocks you from winning, or puts the computer closer to winning, with the attempt at minimizing your chances of winning. That’s why, when playing, if you have 4 in a row, the computer almost always blocks your winning spot, forcing you to adopt a strategy to out-smart the computer.

``````function bestComputerMove(Grid, maxDepth, bestMove) {
let worstResult = -20;
for (let col = 0; col < Grid.length; col++) {
if (isLegalMove(Grid, col)) {
testDrop(Grid, col, 'o');
let result = minHumanScore(Grid, maxDepth, 0);
undoDrop(Grid, col);
if (result > worstResult) {
worstResult = result;
bestMove = col;
}
}
}
return bestMove;

function maxComputerScore(Grid, maxDepth, depth) {
let winner = findWinner(Grid);
if (winner === 'o') {
return 10;
} else if (winner === 'x') {
return -10;
} else if (isBoardFull(Grid) || (depth === maxDepth)) {
return 0;
} else {
let computerBest = -20;
for (let col = 0; col < Grid.length; col++) {
if (isLegalMove(Grid, col)) {
testDrop(Grid, col, 'o');
let result = minHumanScore(Grid, maxDepth, depth + 1);
undoDrop(Grid, col);
if (result > computerBest) {
computerBest = result;
}
}
}
return computerBest;
}

function minHumanScore(Grid, maxDepth, depth) {
let winner = findWinner(Grid);
if (winner === 'o') {
return 10;
} else if (winner === 'x') {
return -10;
} else if (isBoardFull(Grid) || (depth === maxDepth)) {
return 0;
} else {
let humanBest = 20;
for (let col = 0; col < Grid.length; col++) {
if (isLegalMove(Grid, col)) {
testDrop(Grid, col, 'x');
let result = maxComputerScore(Grid, maxDepth, depth + 1);
undoDrop(Grid, col);
if (result < humanBest) {
humanBest = result;
}
}
}
return humanBest;
}
}``````

Currently, the `maxDepth` parameter is set to 6, but testing shows that it can go as high as 8 before the browser crashes. Any value higher than 6, however, seems to make the gameplay extremely slow on the computer’s turn, and anything lower than 5 makes the game too easy to win for human players, and presents no real challenge.

Overall, the game is functional, fun, and somewhat challenging to beat the computer at, and it was an exciting project to adapt a school assignment into a web-based version.