Connect Four (also known as Plot Four, Four In A Row, and Four In A Line) is a two-player board game in which the players take turns in dropping alternating colored discs into a seven-column, six-row vertically-suspended grid. The object of the game is to connect four singly-colored discs in a row - vertically, horizontally, or diagonally -- before your opponent can do likewise.

Your task. Write a Java program that plays the Connect Four game against you. The program

• visualizes the game board in a nice-looking GUI
• accepts point-and-click input from you to specify your next move (i.e. to place a disk into one of the seven columns)
• checks that the proposed move is correct (i.e. the column is not yet full)
• checks if the game is over (see below)
• computes and performs the move of the computer (your opponent)

The Game.

We assume two players for the game: Y and R. Player Y moves the yellow disks, while player R moves the red disks. Further, we assume that R is played by the computer and Y is played by the user (the user enters all input through the program's GUI). Finally, we assume that Y (you, the user) makes the first move in the game.

At any given time the game is in a specific state. A state is determined by the number and position of the red and yellow disks on the board. Note, that for any given state S it can be easily determined which player makes the next move: If state S has more yellow disks than red disks on the board then player R is next; otherwise player Y makes the next move.

Hence, a match can be represented as a sequence of states A₁, A₂, ..., A_n, where the game is advances from one state to the next by means of (legal) moves M_i: A_i->A_i+1.

The game is over if it reaches a state W such that either

• W has four connected same-colored discs in a row: vertically, horizontally, or diagonally. The player with the corresponding color wins the game. Or:
• It is not possible to make another move because the board is full (no free cells left), but none of the two players has won. The game ends remise.

There is an infinite supply of yellow and red disks, i.e. the game never ends because a player runs out of disks.

Visualization.

Your program should draw a nice-looking GUI representation of the game board (see picture) with 7x6 cells (7 vertical columns, 6 horizontal rows). In its initial state, all cells are empty, player Y can make the next (first) move.

As the game progresses, your program should update the game's graphical representation to its current state.

At player Y's turn the program should wait for the user (you) to click on any column of the GUI representation of the board. If the clicked-on column has empty cells, then a yellow disk is added to that column: the disk falls from the top to the bottom-most cell, filling the column from the bottom. Nothing should happen if the clicked-on column does not have any free cells.

At player R's turn the computer chooses a valid move and updates the state and its GUI representation accordingly.

Learning.

Instead of letting the computer choose its moves randomly, we will help it to learn from previous games and avoid mistakes that caused it to loose a previous game.

Player R (the computer) may classify state A as a "lost state" if

1. it is player Y's turn to make the next move, AND
2. player Y makes a move M: A->B and wins the game.

Obviously, R would not wish to ever again come into this "lost state" A, because once the game is in state A then there is nothing that R can do to prevent player Y from repeating its move and win the game.

Furthermore, player R (the computer) may classify another state A as a "lost state" if

1. it is player Y's turn to make the next move, AND
2. player Y makes a move M: A->B such that Y does not win yet, but all moves that R could make in state B would result in states C which are already known to be "lost states". I.e. if the game is in such a state A and if Y makes the correct move, then R has no other choice than making a move that leads to a new state C from which Y can win the game.

Obviously, R would also not wish to ever again come into such a state A again, because once the game is in state A, player Y can make a move that puts R on a loosing track (R is left with no choice but to make a move that leads to a state for which it is already known that Y can definitely win the game).

Maintain a database of "lost states":

Initially, player R (the computer) does not know any "lost states". But every time it looses a game, it learns about a new "lost state". The program should store such states in a database in order to not repeat the same mistakes in the future (i.e. not to make a move that leads to a lost state).

You will notice that our program plays rather naive initially, but will soon become a challenging competitor by learning from you which situations in the game it should avoid.