C Four, miGame, Part 2

I've noticed a lot of searches hitting my blog with my C Four program I made, here. So I'm going to go into a bit of depth about the game now. A lot of the searches say 'Program that proves Connect 4 is a draw'. This got me curious.

Wikipedia says "The game was solved mathematically by James D. Allen (Oct 1, 1988), and independently by Victor Allis (Oct 16, 1988). With perfect play, the first player can force a win by starting in the middle column. By starting in the two adjacent columns, the first player allows the second player to reach a draw; by starting with the four outer columns, the first player allows the second player to force a win."
It also has a couple links to freeware you can download that plays the perfect game. But I'd rather solve it myself.

Lulz

Initial thoughts: So we know the concept, get four in a row either diagonally, horizontally or vertically. The board is 7 long and 6 high. This means that we must use the middle column to get a diagonal or horizontal win. Also a diagonal or vertical win needs the two middle rows. As the board is filled row by row, it become immediately clear that middle board dominance is essential.

More lulz

Could do: I know how to model turn based games on a graph with nodes representing game state and then use logic to determine from what states a player can force a win. But that's boring and very time consuming to do by hand. See xkcd has done this for tic-tac-toe.

Will do: So what I'm going to do instead is alter my old version of C Four (get it? Connect Four but it's written in C so I called it C Four...) and create an AI that uses a depth first recursive search to find the optimum position for the next piece. I could have it build a graph at run time and then traverse the graph with each move made but computers are fast enough to handle what I'm trying to achieve here.
Basic: Make a program that looks at every possible move and picks the best one. 


What I will need:
Time. I'm back from University holidays and my memory is terrible so will have to go back and learn C.
Visual Studio or something similar to develop in. I'm posting at work so will download this to my flash drive and play with the idea from there.
Money. Not for this project but it's always good to have money, am I right?

Even more lulz

Akin to my original C Four program the game is going to be in ASCII. If I am able I will keep C Four as it is and simply add the option to verse a computer player or even watch a computer player verse another computer player. This is where the money is at.

[Connect Flour image. Sorry I lost this one. But it is funny]

If it works correctly we should see the two computer players play the exact same game every time. And hopefully player 1 will always win. That would be pretty cool.

I'm going back into hospital tomorrow for my kidney stones again, but workload from University has lessened so will work on it in my downtime.

Cheers,

C Four, Connect Four, miGame

I'm taking a break from miTanks for a while. Here's one of my first ever programs.

I spend alot of my time in lectures at University playing Connect Four on a piece of paper against friends. This is the best paper game we could come up with. Turn based, so could simply pass notes or signal which column to drop in. And there was no need for an eraser; imaging trying to play chess with a pen.

At the time we were learning C programming and had to come up with some simple program to prove we learnt something in the course. Alot of people went with a Facebook similar 'What animal are you?' kind of game. Boring!

It took about 2-3 hours. Remember this was my first C program I created purely by myself, aside from Visual Basic and MicroWorlds (if that even counts).

Code:

#define _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
//C(onnect) Four
//Created by: Milk
//Date of final build: 19/10/09
//Height of each line
#define LINE_HEIGHT 6
#define LINE_WIDTH 7
void DrawBoard(int grid[LINE_HEIGHT][LINE_WIDTH]);
int CalculateWin(int grid[LINE_HEIGHT][LINE_WIDTH], int player);
int ValidInput(int input, int grid[LINE_HEIGHT][LINE_WIDTH]);
int main(void)
{
 //Plays connect four
 int grid[LINE_HEIGHT][LINE_WIDTH] = {0};
 int gameOver = 0;
 int input = 0;
 int player = 1;
 char inputValid;
 int i;

 //Draw the intitial board (empty)
 DrawBoard(grid);
 while (gameOver == 0 && (grid[LINE_HEIGHT - 1][0] == 0 || grid[LINE_HEIGHT - 1][1] == 0 || grid[LINE_HEIGHT - 1][2] == 0 || grid[LINE_HEIGHT - 1][3] == 0 || grid[LINE_HEIGHT - 1][4] == 0 || grid[LINE_HEIGHT - 1][5] == 0 || grid[LINE_HEIGHT - 1][6] == 0)) {
  //Get input from user
  input = 0;
  printf("\nWhere would you like to go, player %d?\n", player);
  scanf("%d", &input);
  //Decide if input is a valid move
  inputValid = ValidInput(input, grid);
  //If input is not valid prompt for a valid move
  while (inputValid == 0) {
   printf("Please choose a valid position: ");
   scanf("%d", &input);
   inputValid = ValidInput(input, grid);
  }
  //Add input to grid
  for (i = 0; i < LINE_WIDTH; i++) {
   if (grid[i][input - 1] == 0) {
    grid[i][input - 1] = player;
    break;
   }
  }
  //Draw the board
  DrawBoard(grid);
  //Calculate if there is a win
  gameOver = CalculateWin(grid, player);
  //Set the next players turn
  if (player == 1) {
   player = 2;
  } else {
   player = 1;
  }
 }
 //Print winner
 if (gameOver == 0) {
  printf("\n\nThere are no more available moves!\nIt's a draw\n");
 } else {
  printf("\n\nCongratulations player %d!\nYou won\n", gameOver);
 }
 return 0;
}
void DrawBoard(int grid[LINE_HEIGHT][LINE_WIDTH])
{
 //Draws the board
 int i, j;
 printf("\n\n\n\n\n");
 for (i = LINE_HEIGHT - 1; i >= 0; i--) {
  printf("\nI");
  for (j = 0; j < LINE_WIDTH; j++) {
   if (grid[i][j] == 0) {
    printf("   I");
   } else if (grid[i][j] == 1) {
    printf(" X I");
   } else {
    printf(" O I");
   }
  }
 }
 printf("\n__1___2___3___4___5___6___7__");
 return;
}
int ValidInput(int input, int grid[LINE_HEIGHT][LINE_WIDTH])
{
 //Calculate if input is valid
 if (input < 0 || input > 8 || grid[LINE_HEIGHT - 1][input - 1] != 0) {
  return 0;
 } else {
  return 1;
 }
}
int CalculateWin(int grid[LINE_HEIGHT][LINE_WIDTH], int player)
{
 int i, j;
 //Calculate if there is a win on the horizontal
 for (j = 0; j < LINE_WIDTH - 3; j++) {
  for (i = 0; i < LINE_HEIGHT; i++) {
   if (grid[i][j] == grid[i][j + 1] && grid[i][j] == grid[i][j + 2] && grid[i][j] == grid[i][j + 3] && grid[i][j] != 0) {
    return player;
   }
  }
 }
 //Calculate if there is a vertical win
 for (i = 0; i < LINE_HEIGHT - 3; i++) {
  for (j = 0; j < LINE_WIDTH; j++) {
   if (grid[i][j] == grid[i + 1][j] && grid[i][j] == grid[i + 2][j] && grid[i][j] == grid[i + 3][j] && grid[i][j] != 0) {
    return player;
   }
  }
 }
 //Calculate if there is a diagonal up-right win
 for (i = 0; i < LINE_HEIGHT - 3; i++) {
  for (j = 0; j < LINE_WIDTH - 3; j++) {
   if (grid[i][j] == grid[i + 1][j + 1] && grid[i][j] == grid[i + 2][j + 2] && grid[i][j] == grid[i + 3][j + 3] && grid[i][j] != 0) {
    return player;
   }
  }
 }
 //Calculate if there is a diagonal up-left win
 for (i = 0; i < LINE_HEIGHT - 3; i++) {
  for (j = LINE_WIDTH - 1; j >= 0; j--) {
   if (grid[i][j] == grid[i + 1][j - 1] && grid[i][j] == grid[i + 2][j - 2] && grid[i][j] == grid[i + 3][j - 3] && grid[i][j] != 0) {
    return player;
   }
  }
 }
 //No win
 return 0;
}


When compiled the exe file is only 56.0KiB. So it's pretty much always on my USB drive now.
And here it is:
http://rapidshare.com/files/443141503/Connect4.txt
I don't think rapidshare likes exe files so once you download just change the file extension (txt) to exe, and it will work. Give it a go.

Looking back at this code there is not actually too many things I would do differently. Would've been a nice OO exercise though.

If anyone wants to give me a game just tell me your starting move. Let's play. Lol

Cheers,
Milk

Wiki-Hop Blog: Six Degrees

Wiki-Hop Blog: Six Degrees: "Welcome! The purpose of Wiki-Hop is to search for connections between people on Wikipedia.org. Search results ..."

Found this today. Would make playing 6 degrees to Hitler so much easier.