You have a 8x8 board, players take turns placing a piece on any grid. First play
ID: 3917459 • Letter: Y
Question
You have a 8x8 board, players take turns placing a piece on any grid. First player to get 4 in a line (either a row, or a column; diagonals are NOT counted) wins. The maximum amount of time allowed for generating the next move is 30 seconds. At the very beginning, your program should ask the user for the maximum amount time (in seconds) allowed for the computer to generate the answer and make sure that your search will stop when there's no time left. Your program should also ask the user to decide who is going to move first.
In order to make the process smooth, you are REQUIRED to use the following standard in the movement that your program will generate:
Here is a sample program written in C.
Strategies and Other Requirements
To get a full credit, your program must satisfy the requirements listed above, and MUST use alpha-beta pruning to determine the computer's move. Note that, you will need to make some changes to the alpha-beta pruning introduced in the book. These changes include: an evaluation function so that you can evaluate non-terminal states and a cut-off test to replace the terminal test so that your program will return the best solution found so far given a specific period of time.
In general, you are allowed 5 seconds to run your algorithm, which should search at least 5 plies deep. If you use languages other than C or C++, the number of plies may be smaller. You can implement iterative deepening search with alpha-beta pruning so that your program will search as deep as possible given the fixed amount of time.
Given the same amount of time, if your terminal evaluation function is simple, then your program should be able to search deeper than one with a complex (but maybe better) terminal evaluation function. You can decide whether you want a deeper search and a simple evaluation, or a shallower search with a complex evaluation.
Your program is one player, and will attempt to defeat the human operator. Here, "X" means "computer", "O" means "human".
The program should detect when an illegal move has been entered and requires the human to re-enter a valid move, for example, trying to place on a non-empty space, or out of bounds.
Please refer to the tic-tac-toe.cc which implements MINIMAX as the base skeleton to develop the alpha-beta pruning.
A group of 2 is allowed to work on this project. You can also work individually. Your final executable program should be able to run on the computers in the CS labs. The top 3 or 4 teams will receive extra credits. All participants will earn participation credits.
How do two programs interact?
To make the interaction interface easy, your program should output what's the current choice for each step. Each program will run on one computer and the final result will be the opposite of each other. Please see the following illustration. Assume the opponent (the computer) moves first:
Your program running on computer 2: you will need to first input "e5", and then your program should print out the current movement after searching, for example, "d5"
This process will continue until the end of the game.
How to run the tournament?
It depends on the number of groups who are willing to participate. Please let me know your decision on participation by Jun. 3rd.
Here's the strategy we used last time for small number of groups.
Student teams will be arranged into group of 3. The 3 teams will play against each other in the same group. Each match contains two games, with each team moving first. A group will play a total of 6 games. A win counts as 1 point, a draw as .5, and a loss as 0 points. Within each group, whoever has the most points is the winner of the group.
The next round will consist of winner teams from the first round and some 2nd place teams. This process will continue.
Explanation / Answer
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define BOARDMAXROWS 8
#define BOARDMAXCOLS 8
// Function to print the board
void displayBoard(char *board)
{
int row, col;
puts(" **** Connect Four **** ");
// Displays the numbers for column
puts(" 1 2 3 4 5 6 7 8 ");
// Loops till number of rows
for(row = 0; row < BOARDMAXROWS; row++)
{
// Displays alphabet A - H
printf("%c",(65+row));
// Loops till number of columns
for(col = 0; col < BOARDMAXCOLS; col++)
{
// Displays current board value
printf("| %c ", board[BOARDMAXCOLS * row + col]);
}// End of inner for loop
// Displays the column separator
puts("|");
// Displays row separator line
puts(" ---------------------------------");
}// End of outer for loop
}// End of function
// Function to accept the position for a player
int playerMove(char *currentBoard, int currentPlayer, const char *playerSymbol)
{
int row, col = 0;
// Displays message for player number and his symbol
printf("Player %d (%c): Enter number coordinate: ", currentPlayer + 1, playerSymbol[currentPlayer]);
// Loops till valid position
while(1)
{
// Accepts the position from the user
// And checks is less than one or greater than 8 then display error message
if(1 != scanf("%d", &col) || col < 1 || col > 8 )
{
while(getchar() != ' ');
puts("ERROR: Invalid position! Try again.");
}// End of if condition
// Otherwise come out of the loop
else
break;
}// End of while loop
// Decrease the position by one
col--;
// Loops from maximum number of rows to 0
for(row = BOARDMAXROWS - 1; row >= 0; row--)
{
// Checks if the board current position is null
if(currentBoard[BOARDMAXCOLS * row + col] == ' ')
{
// Adds the players symbol to the board
currentBoard[BOARDMAXCOLS * row + col] = playerSymbol[currentPlayer];
// Returns 1 for success
return 1;
}// End of if condition
}// End of outer for loop
// Returns zero for not success
return 0;
}// End of function
// Function to return winning status
int winningStatus(char *currentBoard)
{
// Calls the methods for horizontal, vertical and diagonal win status
return (horizontalFourStatus(currentBoard) || verticalFourStatus(currentBoard) || diagonalFourStatus(currentBoard));
}// End of function
// Function to return one if consecutive four symbols of same type otherwise returns zero
int checkFourStatus(char *board, int a, int b, int c, int d)
{
return (board[a] == board[b] && board[b] == board[c] && board[c] == board[d] && board[a] != ' ');
}// End of function
// Function to returns one if consecutive four symbols of same type in a row
int horizontalFourStatus(char *board)
{
int row, col, index;
const int WIDTH = 1;
// Loops till number of rows
for(row = 0; row < BOARDMAXROWS; row++)
{
// Loops till number of columns minus three
for(col = 0; col < BOARDMAXCOLS - 3; col++)
{
// Extracts the index position
index = BOARDMAXCOLS * row + col;
// Calls the function to check consecutive four of same symbol
if(checkFourStatus(board, index, index + WIDTH, index + WIDTH * 2, index + WIDTH * 3))
{
return 1;
}// End of if condition
}// End of inner for loop
}// End of outer for loop
return 0;
}// End of function
// Function to returns one if consecutive four symbols of same type in a column
int verticalFourStatus(char *board)
{
int row, col, index;
const int HEIGHT = 8;
// Loops till number of rows minus three
for(row = 0; row < BOARDMAXROWS - 3; row++)
{
// Loops till number of columns
for(col = 0; col < BOARDMAXCOLS; col++)
{
// Extracts the index position
index = BOARDMAXCOLS * row + col;
// Calls the function to check consecutive four of same symbol
if(checkFourStatus(board, index, index + HEIGHT, index + HEIGHT * 2, index + HEIGHT * 3))
{
return 1;
}// End of if condition
}// End of inner for loop
}// End of outer for loop
return 0;
}// End of function
// Function to returns one if consecutive four symbols of same type in a diagonal
int diagonalFourStatus(char *board)
{
int row, col, index, counter = 0;
const int rightDiagonal = 6, leftDiagonal = 8;
// Loops till number of rows minus three
for(row = 0; row < BOARDMAXROWS - 3; row++)
{
// Loops till number of columns
for(col = 0; col < BOARDMAXCOLS; col++)
{
// Extracts the index position
index = BOARDMAXCOLS * row + col;
// Calls the function to check consecutive four of same symbol
if(counter <= 3 && checkFourStatus(board, index, index + leftDiagonal, index + leftDiagonal * 2, index + leftDiagonal * 3)
|| counter >= 3 && checkFourStatus(board, index, index + rightDiagonal, index + rightDiagonal * 2, index + rightDiagonal * 3))
{
return 1;
}// End of if condition
// Increase the counter by one
counter++;
}// End of inner for loop
// Resets the counter to zero
counter = 0;
}// End of outer for loop
return 0;
}// End of function
// main function definition
int main()
{
// Creates symbols for the players
const char *playerSymbol = "XO";
// Declares a matrix for the board
char currentBoard[BOARDMAXROWS * BOARDMAXCOLS];
memset(currentBoard, ' ', BOARDMAXROWS * BOARDMAXCOLS);
// Variables for player turn and game over status
int playerTurn, gameComplete = 0;
// Loops till players turn is less than number of cells in the board
// and game is not over
for(playerTurn = 0; playerTurn < BOARDMAXROWS * BOARDMAXCOLS && !gameComplete; playerTurn++)
{
// Calls the function to displays the current board
displayBoard(currentBoard);
while(!playerMove(currentBoard, playerTurn % 2, playerSymbol))
{
// Calls the function to displays the current board
displayBoard(currentBoard);
puts("**Column full! No move available for column.** ");
}// End of while loop
// Calls the function to check the game over status
gameComplete = winningStatus(currentBoard);
}// End of for loop
// Calls the function to displays the current board
displayBoard(currentBoard);
// Checks if players turn is equals to the number of cells in the board
// and game is not over
if(playerTurn == BOARDMAXROWS * BOARDMAXCOLS && !gameComplete)
{
// Display tie
puts("Game Tie!");
}// End of if condition
// Otherwise game not over
else
{
// Decrease the player turn by minus one
playerTurn--;
// Displays the player number with player symbol of the winner
printf("Player %d (%c) wins! ", playerTurn % 2 + 1, playerSymbol[playerTurn % 2]);
}// End of else
return 0;
}// End of main function
Sample Output 1:
**** Connect Four ****
1 2 3 4 5 6 7 8
A| | | | | | | | |
---------------------------------
B| | | | | | | | |
---------------------------------
C| | | | | | | | |
---------------------------------
D| | | | | | | | |
---------------------------------
E| | | | | | | | |
---------------------------------
F| | | | | | | | |
---------------------------------
G| | | | | | | | |
---------------------------------
H| | | | | | | | |
---------------------------------
Player 1 (X):
Enter number coordinate: 1
**** Connect Four ****
1 2 3 4 5 6 7 8
A| | | | | | | | |
---------------------------------
B| | | | | | | | |
---------------------------------
C| | | | | | | | |
---------------------------------
D| | | | | | | | |
---------------------------------
E| | | | | | | | |
---------------------------------
F| | | | | | | | |
---------------------------------
G| | | | | | | | |
---------------------------------
H| X | | | | | | | |
---------------------------------
Player 2 (O):
Enter number coordinate: 2
**** Connect Four ****
1 2 3 4 5 6 7 8
A| | | | | | | | |
---------------------------------
B| | | | | | | | |
---------------------------------
C| | | | | | | | |
---------------------------------
D| | | | | | | | |
---------------------------------
E| | | | | | | | |
---------------------------------
F| | | | | | | | |
---------------------------------
G| | | | | | | | |
---------------------------------
H| X | O | | | | | | |
---------------------------------
Player 1 (X):
Enter number coordinate: 1
**** Connect Four ****
1 2 3 4 5 6 7 8
A| | | | | | | | |
---------------------------------
B| | | | | | | | |
---------------------------------
C| | | | | | | | |
---------------------------------
D| | | | | | | | |
---------------------------------
E| | | | | | | | |
---------------------------------
F| | | | | | | | |
---------------------------------
G| X | | | | | | | |
---------------------------------
H| X | O | | | | | | |
---------------------------------
Player 2 (O):
Enter number coordinate: 3
**** Connect Four ****
1 2 3 4 5 6 7 8
A| | | | | | | | |
---------------------------------
B| | | | | | | | |
---------------------------------
C| | | | | | | | |
---------------------------------
D| | | | | | | | |
---------------------------------
E| | | | | | | | |
---------------------------------
F| | | | | | | | |
---------------------------------
G| X | | | | | | | |
---------------------------------
H| X | O | O | | | | | |
---------------------------------
Player 1 (X):
Enter number coordinate: 1
**** Connect Four ****
1 2 3 4 5 6 7 8
A| | | | | | | | |
---------------------------------
B| | | | | | | | |
---------------------------------
C| | | | | | | | |
---------------------------------
D| | | | | | | | |
---------------------------------
E| | | | | | | | |
---------------------------------
F| X | | | | | | | |
---------------------------------
G| X | | | | | | | |
---------------------------------
H| X | O | O | | | | | |
---------------------------------
Player 2 (O):
Enter number coordinate: 5
**** Connect Four ****
1 2 3 4 5 6 7 8
A| | | | | | | | |
---------------------------------
B| | | | | | | | |
---------------------------------
C| | | | | | | | |
---------------------------------
D| | | | | | | | |
---------------------------------
E| | | | | | | | |
---------------------------------
F| X | | | | | | | |
---------------------------------
G| X | | | | | | | |
---------------------------------
H| X | O | O | | O | | | |
---------------------------------
Player 1 (X):
Enter number coordinate: 1
**** Connect Four ****
1 2 3 4 5 6 7 8
A| | | | | | | | |
---------------------------------
B| | | | | | | | |
---------------------------------
C| | | | | | | | |
---------------------------------
D| | | | | | | | |
---------------------------------
E| X | | | | | | | |
---------------------------------
F| X | | | | | | | |
---------------------------------
G| X | | | | | | | |
---------------------------------
H| X | O | O | | O | | | |
---------------------------------
Player 1 (X) wins!
Sample Output 2:
**** Connect Four ****
1 2 3 4 5 6 7 8
A| | | | | | | | |
---------------------------------
B| | | | | | | | |
---------------------------------
C| | | | | | | | |
---------------------------------
D| | | | | | | | |
---------------------------------
E| | | | | | | | |
---------------------------------
F| | | | | | | | |
---------------------------------
G| | | | | | | | |
---------------------------------
H| | | | | | | | |
---------------------------------
Player 1 (X):
Enter number coordinate: 1
**** Connect Four ****
1 2 3 4 5 6 7 8
A| | | | | | | | |
---------------------------------
B| | | | | | | | |
---------------------------------
C| | | | | | | | |
---------------------------------
D| | | | | | | | |
---------------------------------
E| | | | | | | | |
---------------------------------
F| | | | | | | | |
---------------------------------
G| | | | | | | | |
---------------------------------
H| X | | | | | | | |
---------------------------------
Player 2 (O):
Enter number coordinate: 3
**** Connect Four ****
1 2 3 4 5 6 7 8
A| | | | | | | | |
---------------------------------
B| | | | | | | | |
---------------------------------
C| | | | | | | | |
---------------------------------
D| | | | | | | | |
---------------------------------
E| | | | | | | | |
---------------------------------
F| | | | | | | | |
---------------------------------
G| | | | | | | | |
---------------------------------
H| X | | O | | | | | |
---------------------------------
Player 1 (X):
Enter number coordinate: 1
**** Connect Four ****
1 2 3 4 5 6 7 8
A| | | | | | | | |
---------------------------------
B| | | | | | | | |
---------------------------------
C| | | | | | | | |
---------------------------------
D| | | | | | | | |
---------------------------------
E| | | | | | | | |
---------------------------------
F| | | | | | | | |
---------------------------------
G| X | | | | | | | |
---------------------------------
H| X | | O | | | | | |
---------------------------------
Player 2 (O):
Enter number coordinate: 3
**** Connect Four ****
1 2 3 4 5 6 7 8
A| | | | | | | | |
---------------------------------
B| | | | | | | | |
---------------------------------
C| | | | | | | | |
---------------------------------
D| | | | | | | | |
---------------------------------
E| | | | | | | | |
---------------------------------
F| | | | | | | | |
---------------------------------
G| X | | O | | | | | |
---------------------------------
H| X | | O | | | | | |
---------------------------------
Player 1 (X):
Enter number coordinate: 2
**** Connect Four ****
1 2 3 4 5 6 7 8
A| | | | | | | | |
---------------------------------
B| | | | | | | | |
---------------------------------
C| | | | | | | | |
---------------------------------
D| | | | | | | | |
---------------------------------
E| | | | | | | | |
---------------------------------
F| | | | | | | | |
---------------------------------
G| X | | O | | | | | |
---------------------------------
H| X | X | O | | | | | |
---------------------------------
Player 2 (O):
Enter number coordinate: 3
**** Connect Four ****
1 2 3 4 5 6 7 8
A| | | | | | | | |
---------------------------------
B| | | | | | | | |
---------------------------------
C| | | | | | | | |
---------------------------------
D| | | | | | | | |
---------------------------------
E| | | | | | | | |
---------------------------------
F| | | O | | | | | |
---------------------------------
G| X | | O | | | | | |
---------------------------------
H| X | X | O | | | | | |
---------------------------------
Player 1 (X):
Enter number coordinate: 5
**** Connect Four ****
1 2 3 4 5 6 7 8
A| | | | | | | | |
---------------------------------
B| | | | | | | | |
---------------------------------
C| | | | | | | | |
---------------------------------
D| | | | | | | | |
---------------------------------
E| | | | | | | | |
---------------------------------
F| | | O | | | | | |
---------------------------------
G| X | | O | | | | | |
---------------------------------
H| X | X | O | | X | | | |
---------------------------------
Player 2 (O):
Enter number coordinate: 3
**** Connect Four ****
1 2 3 4 5 6 7 8
A| | | | | | | | |
---------------------------------
B| | | | | | | | |
---------------------------------
C| | | | | | | | |
---------------------------------
D| | | | | | | | |
---------------------------------
E| | | O | | | | | |
---------------------------------
F| | | O | | | | | |
---------------------------------
G| X | | O | | | | | |
---------------------------------
H| X | X | O | | X | | | |
---------------------------------
Player 2 (O) wins!
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.