This assignment concerns implementing an AI agent for playing a two-player game, and is intended to give exposure to planning in the presence of an adversary with a budget on the computation allowed before performing a decision (move).
The standard Connect4 game is a two-player board game. There are two coloured sets of tokens. Each player is assigned a colour. The traditional game is played on a board that is vertical 6x7 (6 rows and 7 columns). A player picks tokens for her/his assigned token and then takes turns for dropping tokens into a specific column in a grid. The pieces fall straight down in the column in which they are inserted and take up the lowest space in the column. The game ends when any one of the players creates one consecutive sequence of their four tokens along a row or along a column or along a diagonal. Some of you may have played this game earlier (see a short video below).
In this assignment, we consider an extension of the standard game (let's name it ExtendedConnect4). The rules and scoring described below.
In ExtendedConnect4, we generalise the board size to (m, n) where the game board dimensions can vary. However, the number of columns (n) will always be even. As in the traditional game, there are two coloured sets of tokens. Each player is assigned a colour.
In ExtendedConnect4, there are standard moves as are there in the standard Connect4 with the additional inclusion of a PopOut Move. Further, there is a time budget for making a move. These are described next:
The animation below shows an example game progression. Here, Player 1 is using the yellow coloured tokens and Player 2 is using with the red coloured tokens.
Unlike traditional Connect4, a game of ExtendedConnect4 does not stop upon completion of the first sequence of four consecutive tokens. Instead, the game continues till there is a stalemate is reached, i.e., there are no possible moves left for any player.