J
JB Cardenas
Hello all, attached to this message is my code for a Tic Tac Toe game,
this game plays with the strategy Minimax and Minimax Alpha Beta
Prunnig. Somebody can review my code to find errors and to test my
algorithms.
Thanks,
Jairo Cárdenas
*************************My Code Begin Here***********************
//**************************************************************************//
//
//
// Author: Jairo A. Cardenas
//
// Date: 11/10/2003
//
// Version: 2.0
//
//
//
//**************************************************************************//
// Author: Jairo A. Cardenas
// Student # F01082069
// Compiler: Turbo C++ 3.0
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <conio.h>
#include <ctype.h>
#define ancho_tablero 3
#define numero_de_cuadros 9
int cierto= 1;
int falso= 0;
/* in each square of the board there is always an element that it can
be O,0, X*/
enum simbolo {vacio = 0, X, O};
typedef enum simbolo contenido_del_cuadro;
/*The States found after the recursive search are lost, win, draw*/
enum estado {pierde, empata, gana};
typedef enum estado estado_del_juego;
/* structure that models the board. */
/*This is a vector with as many positions as will be the value of
numero_de_cuadros*/
struct cuadricula {
contenido_del_cuadro cuadro[numero_de_cuadros];
int cuadros_ocupados;
};
/* type of data of the board*/
typedef struct cuadricula tipo_tablero;
/* this variable keeps the letter with the human player palys*/
char letra_para_jugar;
/* this variable keeps a 'C' if the first that plays is the computer
of the contrary keeps a 'H'*/
char primero_en_jugar;
/*this variable keeps a '1' if play tic tac toe using the strategy
minimax, and '2' if play using minimax with alphabeta pruning*/
char minimax_o_alfabeta;
/*Store the name of the player*/
char jugador[40];
/*this function puts a zero(0) on each one of the positions of the
board*/
void iniciar_tablero (tipo_tablero * tablero);
/*draw the board in the screen*/
void mostrar_tablero1 (tipo_tablero tablero,int valcol,int valfila);
/* draw the lines of the board*/
void ponercuadro(int valcol,int valfila);
/*read from the console the content of the variable etra_para_jugar*/
char primer_menu (void);
/*stop the operating of the program by a moment*/
void pulsar_tecla_para_continuar (void);
/*read the name of the player and who plays first*/
void otros_datos();
/*maintain the cycle of the game*/
void jugar();
/*read a character from the console or screen*/
char capturar_caracter (char* letrero);
/*puts a X or O on the indicated position of the board*/
void marcar_el_tablero (tipo_tablero * tablero, int posicion,
contenido_del_cuadro figura_activa);
/*requests to the human that it writes the coordinates of the position
that is going to play*/
int capturar_jugada (tipo_tablero tablero, int linea);
/* determine if the board is full*/
int esta_lleno_el_tablero (tipo_tablero tablero);
/*determine if there is a winner*/
int hay_ganador (tipo_tablero tablero);
/*feature that returns the position in the one which plays the
computer*/
int encontrar_la_mejor_jugada (tipo_tablero tablero,
contenido_del_cuadro figura_activa);
/*function for the search using minimax with alpha beta pruning */
int alfabeta_computador (tipo_tablero tablero,contenido_del_cuadro
figura_activa, estado_del_juego *estadox, estado_del_juego
alfa,estado_del_juego beta);
void alfabeta_humano (tipo_tablero tablero,contenido_del_cuadro
figura_activa, estado_del_juego *estadox, estado_del_juego
alfa,estado_del_juego beta);
/*function for the search using minimax*/
int minimax_computador (tipo_tablero tablero,contenido_del_cuadro\0
figura_activa,
estado_del_juego *estadox,estado_del_juego li,estado_del_juego ls);
void minimax_humano (tipo_tablero tablero,contenido_del_cuadro
figura_activa,
estado_del_juego *estadox,estado_del_juego li,estado_del_juego ls);
/* puts on zero the board, clear the board*/
void borrar_figura (tipo_tablero * tablero, int lugar);
void main(void)
{
char seguir_jugando='Y';
clrscr();
gotoxy(5,10);
printf ("Write your Name: ");
scanf(" %[^\n]",jugador);/* Se traduce la palabra jugador?? oesa
Player*/
clrscr();
minimax_o_alfabeta=primer_menu();
while (minimax_o_alfabeta!='3')
{
randomize();
while(seguir_jugando=='Y')
{
otros_datos();
jugar( );
seguir_jugando=capturar_caracter("\nDo you want to play one more
time? YES[Y], NO[Any Key]");
}
minimax_o_alfabeta=primer_menu();
seguir_jugando='Y';
}
}
void iniciar_tablero (tipo_tablero * tablero)
{
int i;
for (i = 0; i < numero_de_cuadros; i++)
{
tablero->cuadro = vacio;
}
tablero->cuadros_ocupados = 0;
}
/* end iniciar_tablero */
/* Function Show Board*/
void mostrar_tablero1 (tipo_tablero tablero, int valcol,int valfila)
{
int i,j,col,fila;
col=valcol;
fila=valfila;
/*clrscr();*/ /* si no se require se quita*/
for(i=0;i<ancho_tablero;i++)
{
for(j=0;j<ancho_tablero;j++)
{
gotoxy(col,fila);
switch (tablero.cuadro[ancho_tablero*i+j])
{
case X:
printf (" X ");
break;
case O:
printf (" O ");
break;
case vacio:
printf (" ");
break;
default:
printf (" ");
}
col=col+5;
}
fila=fila+2;
col=valcol;
}
ponercuadro(valcol-1,valfila-1);
}
/* end mostrar_tablero */
void ponercuadro(int valcol,int valfila)
{
int i,j,fila,col;
fila=valfila;
col=valcol;
for(i=1;i<=ancho_tablero+1;i++)
{
gotoxy(col-1,fila+1);
if (i<ancho_tablero+1) printf("%d",i);
gotoxy(col,fila);
printf("----------------");
fila=fila+2;
}
col=valcol;
fila=valfila;
for(i=1;i<=ancho_tablero+1;i++)
{
gotoxy(col+2,fila-1);
if (i<ancho_tablero+1) printf("%d",i);
for (j=1;j<=2*ancho_tablero+1;j++)
{
gotoxy(col,fila);printf("|");
fila=fila+1;
}
col=col+5;
fila=valfila;
}
}
/* end ponercuadrado */
/**main menu*****/
char primer_menu (void)
{
char op;
do
{
clrscr ();
printf (" TIC - TAC - TOE\n");
printf (" ===============\n");
printf ("\n");
printf (" Author : Jairo Alberto Cardenas\n");
printf (" 1. Minimax Strategy \n");
printf (" 2. Minimax with Alpha Beta Prunning Strategy\n");
printf (" 3. Exit.\n");
printf ("\n");
op=capturar_caracter("Select the Option: ");
}
while(op!='1' && op!='2' && op!='3');
return op;
}
/*end main menu*/
/*Define other data as name of the player*/
void otros_datos()
{
clrscr();
gotoxy(1,1);
printf("%s%s",jugador," WELCOME TO THE GAME ");
if( minimax_o_alfabeta =='1')
printf("PLAYING TIC TAC TOE USING THE MINIMAX STRATEGY\n");
else
printf("PLAYING TIC TAC TOE USING THE MINIMAX WITH ALPHA BETA
PRUNNING\n");
do
{
gotoxy(1,3);
primero_en_jugar=capturar_caracter("Who Plays First? The Computer[C]
or Human[H] ");
primero_en_jugar=toupper(primero_en_jugar);
}
while(primero_en_jugar!='H'&& primero_en_jugar!='C');
do
{
gotoxy(1,4);
letra_para_jugar=capturar_caracter("With which letter wants to Play
'X' or 'O'? ");
letra_para_jugar=toupper(letra_para_jugar);
}
while(letra_para_jugar!='X'&& letra_para_jugar!='O');
}
/*end otros_datos*/
/* function to read character*/
char capturar_caracter (char* letrero)
{
char aux;
printf ("%s", letrero);
scanf ("%c", &aux);
aux = toupper (aux);
fflush (stdin);
return aux;
}
/* end capturar_caracter */
/*function Play*/
void jugar()
{
tipo_tablero tablero;
int se_acabo;
char turno;
int juega_en_la_posicion,indice, fila,x,y;
contenido_del_cuadro figura_activa;
int j;
j=0;
se_acabo=falso;
if (primero_en_jugar=='C')
turno='C';
else
{
turno='H';
}
clrscr();
fila=4;
iniciar_tablero (&tablero);
mostrar_tablero1 (tablero,5,fila);
j++;
while(se_acabo==falso)
{
if (turno=='C')
{
/*turn for the computer*/
figura_activa= (letra_para_jugar=='X')? O:X;
juega_en_la_posicion=encontrar_la_mejor_jugada (tablero,
figura_activa);
x=(juega_en_la_posicion % ancho_tablero)+1;
y=(juega_en_la_posicion / ancho_tablero)+1;
marcar_el_tablero (&tablero,juega_en_la_posicion,figura_activa);
if (j==2)
{
pulsar_tecla_para_continuar();
j=0;
fila=5;
clrscr();
}
else
{
fila=fila+10;
}
printf("\nThe Computer plays in:");printf ("(%d, %d)\n", x, y);
mostrar_tablero1 (tablero,5,fila);
j++;
}
else
/*turn for the human*/
{
figura_activa= (letra_para_jugar=='X')? X:O;
if (tablero.cuadros_ocupados == (numero_de_cuadros - 1))
{
juega_en_la_posicion = 0;
while (tablero.cuadro[juega_en_la_posicion] != vacio)
juega_en_la_posicion++;
}
else
{
juega_en_la_posicion = capturar_jugada(tablero,fila+7);
}
marcar_el_tablero
(&tablero,juega_en_la_posicion,figura_activa);
}
if (j==2)
{
pulsar_tecla_para_continuar();
j=0;
fila=5;
clrscr();
}
else
{
fila=fila+10;
}
mostrar_tablero1 (tablero,5,fila);
j++;
if (hay_ganador (tablero)==cierto)
{
printf ("\nThe WINNER IS ... ");
if(turno =='C')
printf( "!!!The Computer!!!");
else
printf("!!!The Human!!!!");
se_acabo = cierto;
}
else
{
if (esta_lleno_el_tablero (tablero)==cierto)
{
printf ("\nGame is Daw");
se_acabo = cierto;
} /* end if esta_lleno_el_tablero */
else
{
/* chage the turn */
turno = ((turno =='C') ?'H' : 'C');
}
}
}/*fin of while*/
}/*fin of play()*/
void marcar_el_tablero (tipo_tablero * tablero, int posicion,
contenido_del_cuadro figura_activa)
{
tablero->cuadro[posicion] = figura_activa;
(tablero->cuadros_ocupados)++;
} /* end of marcar el tablero */
/* function to read play */
int capturar_jugada (tipo_tablero tablero, int linea)
{
int columna, fila, posicion;
int ok;
do {
gotoxy(1,linea);
printf ("Write the position in which is going to
play(column,row) : ", numero_de_cuadros);
scanf ("%d,%d", &columna, &fila);
fflush (stdin);
/* go from matrix position to vector position*/
posicion = (columna - 1) + ancho_tablero * (fila - 1);
if ((posicion < 0) || (posicion >= numero_de_cuadros) ||
(tablero.cuadro[posicion] != vacio)) {
gotoxy(1,linea);printf ("
");
gotoxy(1,linea); printf ("This position is occupied or it is
not enables, press enter");getch();
gotoxy(1,linea);printf ("
");
ok = falso;
}
else {
ok = cierto;
}
} while ( ok==falso);
return posicion;
} /*end of function to read play*/
/* Function the board is full*/
int esta_lleno_el_tablero (tipo_tablero tablero)
{
if (tablero.cuadros_ocupados == numero_de_cuadros)
{
return cierto;
}
else
{
return falso;
}
}
/* end of esta_lleno_el_tablero*/
/*function find the best movement*/
int encontrar_la_mejor_jugada (tipo_tablero tablero,
contenido_del_cuadro figura_activa)
{
int esquinas[4];
int mejor_jugada, esquina, pos_inicial,i;
int ocupado;
estado_del_juego estadox;
esquinas[0]=0;
esquinas[1]= ancho_tablero - 1 ;
esquinas[2]=numero_de_cuadros - ancho_tablero;
esquinas[3] =numero_de_cuadros - 1;
randomize();
pos_inicial=0;
if (tablero.cuadros_ocupados == 0)
{
/* There is no full squares. then play in the left upper
corner*/
mejor_jugada = pos_inicial;
}
else
{
if (tablero.cuadros_ocupados == 1)
{
if (tablero.cuadro[pos_inicial] == vacio)
{
mejor_jugada = pos_inicial;
}
else
{
/* if the left upper corner is occupied, search other corner */
ocupado = falso;
do
{
/* choose a corner */
esquina = esquinas[random (4)];
if (tablero.cuadro[esquina] != vacio)
{ ocupado = cierto; }
else
{ocupado=falso;}
} while (ocupado==cierto || esquina==(ancho_tablero - 1));
mejor_jugada = esquina;
} /* end if else - primer cuadro lleno*/
}
else
{
/* 2 or more squares are already marked */
/* call minimax or minimax with alpha-beta pruning */
if (minimax_o_alfabeta=='1')
{
mejor_jugada=minimax_computador(tablero,figura_activa,&estadox,-10,10);
}
if (minimax_o_alfabeta=='2')
{
mejor_jugada = alfabeta_computador(tablero, figura_activa, &estadox,
-10, 10);
}
}
}
return mejor_jugada;
} /* end find the best movement */
/*Function that indicates if there is a winner*/
int hay_ganador (tipo_tablero tablero)
{
int i, posicion;
int cadena;
int ganador = falso;
/* check rows */
posicion = 0;
while ((ganador==falso) && (posicion < numero_de_cuadros))
{
cadena = tablero.cuadro[posicion];
/* verifica que en cada fila haya ocurrencias de la misma figura
'X' o 'O' */
for (i = (posicion + 1); i < (posicion + ancho_tablero); i++)
cadena = cadena & tablero.cuadro;
ganador = (cadena != vacio) ? cierto : falso;
posicion += ancho_tablero;
} /* fin while - que revisa filas */
/* check columns */
posicion = 0;
while ((ganador==falso) && (posicion < ancho_tablero)) {
cadena = tablero.cuadro[posicion];
/*check that in each column there are occurrences of the same figure
'X' or 'O' */
for (i = (posicion + ancho_tablero); i < numero_de_cuadros; i +=
ancho_tablero)
cadena = cadena & tablero.cuadro;
ganador = (cadena != vacio) ? cierto : falso;
posicion++;
} /* end while - check columns */
/* check diagonals */
/* diagonal from left upper corner */
if (ganador==falso) {
cadena = tablero.cuadro[0];
for (i = (ancho_tablero + 1); i < numero_de_cuadros; i +=
(ancho_tablero + 1))
cadena = cadena & tablero.cuadro;
ganador = (cadena != vacio) ? cierto : falso;
}
/* diagonal from right upper corner */
if (ganador==falso) {
cadena = tablero.cuadro[ancho_tablero - 1];
for (i = (2 * ancho_tablero - 2); i < (numero_de_cuadros - 1);
i += (ancho_tablero - 1))
cadena = cadena & tablero.cuadro;
ganador = (cadena != vacio) ? cierto : falso;
} /* end if */
return ganador;
}
/* fin hay ganador */
/* Function Alpha Beta for Computer Player*/
int alfabeta_computador (tipo_tablero tablero,contenido_del_cuadro
figura_activa,
estado_del_juego *estadox,estado_del_juego alfa,estado_del_juego beta)
{
int i, mejor_jugada;
estado_del_juego turno_actual;
if (hay_ganador (tablero)==cierto)
{
/* The human win with the last play */
*estadox = pierde;
}
else
{
if (esta_lleno_el_tablero(tablero)==cierto)
{
/* the game is over */
*estadox = empata;
}
else
{
/* here it begins the recursive search */
*estadox = alfa;
for (i = 0; (i < numero_de_cuadros) && (*estadox < beta); i++)
{
if (tablero.cuadro == vacio)
{
marcar_el_tablero (&tablero, i, figura_activa);
alfabeta_humano (tablero, ((figura_activa == X) ? O : X),
&turno_actual, *estadox, beta);
borrar_figura (&tablero, i);
if (turno_actual > *estadox)
{
/* found a better move for a player */
*estadox = turno_actual;
mejor_jugada = i;
}
}
}
}
}
return mejor_jugada;
}
/* end of alfabeta computador*/
/* Function Alpha Beta Human*/
void alfabeta_humano (tipo_tablero tablero,
contenido_del_cuadro figura_activa, estado_del_juego *estadox,
estado_del_juego alfa,estado_del_juego beta)
{
int i, auxiliar;
contenido_del_cuadro turno_actual;
if (hay_ganador (tablero)==cierto) {
/* goal state amd terminal case, player has won by last move */
*estadox = gana;
}
else {
if (esta_lleno_el_tablero (tablero)==cierto) {
/* terminal case */
*estadox = empata;
}
else {
/* recursive search */
*estadox = beta;
for (i = 0; (i < numero_de_cuadros) && (*estadox > alfa) ; i++) {
if (tablero.cuadro == vacio) {
marcar_el_tablero (&tablero, i,figura_activa);
auxiliar = alfabeta_computador (tablero, ((figura_activa == X)
? O : X),
&turno_actual, alfa, *estadox);
borrar_figura (&tablero, i);
if (turno_actual < *estadox) {
*estadox = turno_actual;
}
}
}
}
}
}
/* fin alfabeta_humano */
/*Function Clear Figure*/
void borrar_figura (tipo_tablero * tablero, int lugar)
{
if (tablero->cuadro[lugar] != vacio) {
tablero->cuadro[lugar] =vacio;
--(tablero->cuadros_ocupados);
} /* end if */
}
/* end of borrar figura*/
void pulsar_tecla_para_continuar(void)
{
printf("\nPress any key to continue\n");
getch();
}
/* Fuction Minimax for Computer Player*/
int minimax_computador (tipo_tablero tablero,contenido_del_cuadro
figura_activa,
estado_del_juego *estadox,estado_del_juego li,estado_del_juego ls)
{
int i, mejor_jugada;
estado_del_juego turno_actual;
if (hay_ganador (tablero)==cierto) {
*estadox = pierde;
}
else {
if (esta_lleno_el_tablero(tablero)==cierto) {
*estadox = empata;
}
else {
*estadox=li;
for (i = 0; i< numero_de_cuadros ; i++) {
if (tablero.cuadro == vacio) {
marcar_el_tablero (&tablero, i, figura_activa);
minimax_humano (tablero, ((figura_activa == X) ? O : X),
&turno_actual,*estadox, ls);
borrar_figura (&tablero, i);
if (turno_actual > *estadox) {
*estadox = turno_actual;
mejor_jugada = i;
}
}
}
}
}
return mejor_jugada;
}
/*fin minimax computador*/
/*Function Minimax for Human Player*/
void minimax_humano (tipo_tablero tablero,
contenido_del_cuadro figura_activa, estado_del_juego
*estadox,estado_del_juego li,estado_del_juego ls)
{
int i, auxiliar;
contenido_del_cuadro turno_actual;
if (hay_ganador (tablero)==cierto) {
/* goal state amd terminal case, player has won by last move */
*estadox = gana;
}
else {
if (esta_lleno_el_tablero (tablero)==cierto) {
/* terminal case */
*estadox = empata;
}
else {
/*
recursive search
*/
*estadox=ls;
for (i = 0; i < numero_de_cuadros ; i++)
{
if (tablero.cuadro == vacio)
{
marcar_el_tablero (&tablero, i,figura_activa);
auxiliar = minimax_computador (tablero, ((figura_activa == X)
? O : X),
&turno_actual,li,*estadox);
borrar_figura (&tablero, i);
if (turno_actual < *estadox)
{
*estadox = turno_actual;
}
}
}
}
}
}
/* end of minimax_humano */
**********************My Code End Here**************************
this game plays with the strategy Minimax and Minimax Alpha Beta
Prunnig. Somebody can review my code to find errors and to test my
algorithms.
Thanks,
Jairo Cárdenas
*************************My Code Begin Here***********************
//**************************************************************************//
//
//
// Author: Jairo A. Cardenas
//
// Date: 11/10/2003
//
// Version: 2.0
//
//
//
//**************************************************************************//
// Author: Jairo A. Cardenas
// Student # F01082069
// Compiler: Turbo C++ 3.0
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <conio.h>
#include <ctype.h>
#define ancho_tablero 3
#define numero_de_cuadros 9
int cierto= 1;
int falso= 0;
/* in each square of the board there is always an element that it can
be O,0, X*/
enum simbolo {vacio = 0, X, O};
typedef enum simbolo contenido_del_cuadro;
/*The States found after the recursive search are lost, win, draw*/
enum estado {pierde, empata, gana};
typedef enum estado estado_del_juego;
/* structure that models the board. */
/*This is a vector with as many positions as will be the value of
numero_de_cuadros*/
struct cuadricula {
contenido_del_cuadro cuadro[numero_de_cuadros];
int cuadros_ocupados;
};
/* type of data of the board*/
typedef struct cuadricula tipo_tablero;
/* this variable keeps the letter with the human player palys*/
char letra_para_jugar;
/* this variable keeps a 'C' if the first that plays is the computer
of the contrary keeps a 'H'*/
char primero_en_jugar;
/*this variable keeps a '1' if play tic tac toe using the strategy
minimax, and '2' if play using minimax with alphabeta pruning*/
char minimax_o_alfabeta;
/*Store the name of the player*/
char jugador[40];
/*this function puts a zero(0) on each one of the positions of the
board*/
void iniciar_tablero (tipo_tablero * tablero);
/*draw the board in the screen*/
void mostrar_tablero1 (tipo_tablero tablero,int valcol,int valfila);
/* draw the lines of the board*/
void ponercuadro(int valcol,int valfila);
/*read from the console the content of the variable etra_para_jugar*/
char primer_menu (void);
/*stop the operating of the program by a moment*/
void pulsar_tecla_para_continuar (void);
/*read the name of the player and who plays first*/
void otros_datos();
/*maintain the cycle of the game*/
void jugar();
/*read a character from the console or screen*/
char capturar_caracter (char* letrero);
/*puts a X or O on the indicated position of the board*/
void marcar_el_tablero (tipo_tablero * tablero, int posicion,
contenido_del_cuadro figura_activa);
/*requests to the human that it writes the coordinates of the position
that is going to play*/
int capturar_jugada (tipo_tablero tablero, int linea);
/* determine if the board is full*/
int esta_lleno_el_tablero (tipo_tablero tablero);
/*determine if there is a winner*/
int hay_ganador (tipo_tablero tablero);
/*feature that returns the position in the one which plays the
computer*/
int encontrar_la_mejor_jugada (tipo_tablero tablero,
contenido_del_cuadro figura_activa);
/*function for the search using minimax with alpha beta pruning */
int alfabeta_computador (tipo_tablero tablero,contenido_del_cuadro
figura_activa, estado_del_juego *estadox, estado_del_juego
alfa,estado_del_juego beta);
void alfabeta_humano (tipo_tablero tablero,contenido_del_cuadro
figura_activa, estado_del_juego *estadox, estado_del_juego
alfa,estado_del_juego beta);
/*function for the search using minimax*/
int minimax_computador (tipo_tablero tablero,contenido_del_cuadro\0
figura_activa,
estado_del_juego *estadox,estado_del_juego li,estado_del_juego ls);
void minimax_humano (tipo_tablero tablero,contenido_del_cuadro
figura_activa,
estado_del_juego *estadox,estado_del_juego li,estado_del_juego ls);
/* puts on zero the board, clear the board*/
void borrar_figura (tipo_tablero * tablero, int lugar);
void main(void)
{
char seguir_jugando='Y';
clrscr();
gotoxy(5,10);
printf ("Write your Name: ");
scanf(" %[^\n]",jugador);/* Se traduce la palabra jugador?? oesa
Player*/
clrscr();
minimax_o_alfabeta=primer_menu();
while (minimax_o_alfabeta!='3')
{
randomize();
while(seguir_jugando=='Y')
{
otros_datos();
jugar( );
seguir_jugando=capturar_caracter("\nDo you want to play one more
time? YES[Y], NO[Any Key]");
}
minimax_o_alfabeta=primer_menu();
seguir_jugando='Y';
}
}
void iniciar_tablero (tipo_tablero * tablero)
{
int i;
for (i = 0; i < numero_de_cuadros; i++)
{
tablero->cuadro = vacio;
}
tablero->cuadros_ocupados = 0;
}
/* end iniciar_tablero */
/* Function Show Board*/
void mostrar_tablero1 (tipo_tablero tablero, int valcol,int valfila)
{
int i,j,col,fila;
col=valcol;
fila=valfila;
/*clrscr();*/ /* si no se require se quita*/
for(i=0;i<ancho_tablero;i++)
{
for(j=0;j<ancho_tablero;j++)
{
gotoxy(col,fila);
switch (tablero.cuadro[ancho_tablero*i+j])
{
case X:
printf (" X ");
break;
case O:
printf (" O ");
break;
case vacio:
printf (" ");
break;
default:
printf (" ");
}
col=col+5;
}
fila=fila+2;
col=valcol;
}
ponercuadro(valcol-1,valfila-1);
}
/* end mostrar_tablero */
void ponercuadro(int valcol,int valfila)
{
int i,j,fila,col;
fila=valfila;
col=valcol;
for(i=1;i<=ancho_tablero+1;i++)
{
gotoxy(col-1,fila+1);
if (i<ancho_tablero+1) printf("%d",i);
gotoxy(col,fila);
printf("----------------");
fila=fila+2;
}
col=valcol;
fila=valfila;
for(i=1;i<=ancho_tablero+1;i++)
{
gotoxy(col+2,fila-1);
if (i<ancho_tablero+1) printf("%d",i);
for (j=1;j<=2*ancho_tablero+1;j++)
{
gotoxy(col,fila);printf("|");
fila=fila+1;
}
col=col+5;
fila=valfila;
}
}
/* end ponercuadrado */
/**main menu*****/
char primer_menu (void)
{
char op;
do
{
clrscr ();
printf (" TIC - TAC - TOE\n");
printf (" ===============\n");
printf ("\n");
printf (" Author : Jairo Alberto Cardenas\n");
printf (" 1. Minimax Strategy \n");
printf (" 2. Minimax with Alpha Beta Prunning Strategy\n");
printf (" 3. Exit.\n");
printf ("\n");
op=capturar_caracter("Select the Option: ");
}
while(op!='1' && op!='2' && op!='3');
return op;
}
/*end main menu*/
/*Define other data as name of the player*/
void otros_datos()
{
clrscr();
gotoxy(1,1);
printf("%s%s",jugador," WELCOME TO THE GAME ");
if( minimax_o_alfabeta =='1')
printf("PLAYING TIC TAC TOE USING THE MINIMAX STRATEGY\n");
else
printf("PLAYING TIC TAC TOE USING THE MINIMAX WITH ALPHA BETA
PRUNNING\n");
do
{
gotoxy(1,3);
primero_en_jugar=capturar_caracter("Who Plays First? The Computer[C]
or Human[H] ");
primero_en_jugar=toupper(primero_en_jugar);
}
while(primero_en_jugar!='H'&& primero_en_jugar!='C');
do
{
gotoxy(1,4);
letra_para_jugar=capturar_caracter("With which letter wants to Play
'X' or 'O'? ");
letra_para_jugar=toupper(letra_para_jugar);
}
while(letra_para_jugar!='X'&& letra_para_jugar!='O');
}
/*end otros_datos*/
/* function to read character*/
char capturar_caracter (char* letrero)
{
char aux;
printf ("%s", letrero);
scanf ("%c", &aux);
aux = toupper (aux);
fflush (stdin);
return aux;
}
/* end capturar_caracter */
/*function Play*/
void jugar()
{
tipo_tablero tablero;
int se_acabo;
char turno;
int juega_en_la_posicion,indice, fila,x,y;
contenido_del_cuadro figura_activa;
int j;
j=0;
se_acabo=falso;
if (primero_en_jugar=='C')
turno='C';
else
{
turno='H';
}
clrscr();
fila=4;
iniciar_tablero (&tablero);
mostrar_tablero1 (tablero,5,fila);
j++;
while(se_acabo==falso)
{
if (turno=='C')
{
/*turn for the computer*/
figura_activa= (letra_para_jugar=='X')? O:X;
juega_en_la_posicion=encontrar_la_mejor_jugada (tablero,
figura_activa);
x=(juega_en_la_posicion % ancho_tablero)+1;
y=(juega_en_la_posicion / ancho_tablero)+1;
marcar_el_tablero (&tablero,juega_en_la_posicion,figura_activa);
if (j==2)
{
pulsar_tecla_para_continuar();
j=0;
fila=5;
clrscr();
}
else
{
fila=fila+10;
}
printf("\nThe Computer plays in:");printf ("(%d, %d)\n", x, y);
mostrar_tablero1 (tablero,5,fila);
j++;
}
else
/*turn for the human*/
{
figura_activa= (letra_para_jugar=='X')? X:O;
if (tablero.cuadros_ocupados == (numero_de_cuadros - 1))
{
juega_en_la_posicion = 0;
while (tablero.cuadro[juega_en_la_posicion] != vacio)
juega_en_la_posicion++;
}
else
{
juega_en_la_posicion = capturar_jugada(tablero,fila+7);
}
marcar_el_tablero
(&tablero,juega_en_la_posicion,figura_activa);
}
if (j==2)
{
pulsar_tecla_para_continuar();
j=0;
fila=5;
clrscr();
}
else
{
fila=fila+10;
}
mostrar_tablero1 (tablero,5,fila);
j++;
if (hay_ganador (tablero)==cierto)
{
printf ("\nThe WINNER IS ... ");
if(turno =='C')
printf( "!!!The Computer!!!");
else
printf("!!!The Human!!!!");
se_acabo = cierto;
}
else
{
if (esta_lleno_el_tablero (tablero)==cierto)
{
printf ("\nGame is Daw");
se_acabo = cierto;
} /* end if esta_lleno_el_tablero */
else
{
/* chage the turn */
turno = ((turno =='C') ?'H' : 'C');
}
}
}/*fin of while*/
}/*fin of play()*/
void marcar_el_tablero (tipo_tablero * tablero, int posicion,
contenido_del_cuadro figura_activa)
{
tablero->cuadro[posicion] = figura_activa;
(tablero->cuadros_ocupados)++;
} /* end of marcar el tablero */
/* function to read play */
int capturar_jugada (tipo_tablero tablero, int linea)
{
int columna, fila, posicion;
int ok;
do {
gotoxy(1,linea);
printf ("Write the position in which is going to
play(column,row) : ", numero_de_cuadros);
scanf ("%d,%d", &columna, &fila);
fflush (stdin);
/* go from matrix position to vector position*/
posicion = (columna - 1) + ancho_tablero * (fila - 1);
if ((posicion < 0) || (posicion >= numero_de_cuadros) ||
(tablero.cuadro[posicion] != vacio)) {
gotoxy(1,linea);printf ("
");
gotoxy(1,linea); printf ("This position is occupied or it is
not enables, press enter");getch();
gotoxy(1,linea);printf ("
");
ok = falso;
}
else {
ok = cierto;
}
} while ( ok==falso);
return posicion;
} /*end of function to read play*/
/* Function the board is full*/
int esta_lleno_el_tablero (tipo_tablero tablero)
{
if (tablero.cuadros_ocupados == numero_de_cuadros)
{
return cierto;
}
else
{
return falso;
}
}
/* end of esta_lleno_el_tablero*/
/*function find the best movement*/
int encontrar_la_mejor_jugada (tipo_tablero tablero,
contenido_del_cuadro figura_activa)
{
int esquinas[4];
int mejor_jugada, esquina, pos_inicial,i;
int ocupado;
estado_del_juego estadox;
esquinas[0]=0;
esquinas[1]= ancho_tablero - 1 ;
esquinas[2]=numero_de_cuadros - ancho_tablero;
esquinas[3] =numero_de_cuadros - 1;
randomize();
pos_inicial=0;
if (tablero.cuadros_ocupados == 0)
{
/* There is no full squares. then play in the left upper
corner*/
mejor_jugada = pos_inicial;
}
else
{
if (tablero.cuadros_ocupados == 1)
{
if (tablero.cuadro[pos_inicial] == vacio)
{
mejor_jugada = pos_inicial;
}
else
{
/* if the left upper corner is occupied, search other corner */
ocupado = falso;
do
{
/* choose a corner */
esquina = esquinas[random (4)];
if (tablero.cuadro[esquina] != vacio)
{ ocupado = cierto; }
else
{ocupado=falso;}
} while (ocupado==cierto || esquina==(ancho_tablero - 1));
mejor_jugada = esquina;
} /* end if else - primer cuadro lleno*/
}
else
{
/* 2 or more squares are already marked */
/* call minimax or minimax with alpha-beta pruning */
if (minimax_o_alfabeta=='1')
{
mejor_jugada=minimax_computador(tablero,figura_activa,&estadox,-10,10);
}
if (minimax_o_alfabeta=='2')
{
mejor_jugada = alfabeta_computador(tablero, figura_activa, &estadox,
-10, 10);
}
}
}
return mejor_jugada;
} /* end find the best movement */
/*Function that indicates if there is a winner*/
int hay_ganador (tipo_tablero tablero)
{
int i, posicion;
int cadena;
int ganador = falso;
/* check rows */
posicion = 0;
while ((ganador==falso) && (posicion < numero_de_cuadros))
{
cadena = tablero.cuadro[posicion];
/* verifica que en cada fila haya ocurrencias de la misma figura
'X' o 'O' */
for (i = (posicion + 1); i < (posicion + ancho_tablero); i++)
cadena = cadena & tablero.cuadro;
ganador = (cadena != vacio) ? cierto : falso;
posicion += ancho_tablero;
} /* fin while - que revisa filas */
/* check columns */
posicion = 0;
while ((ganador==falso) && (posicion < ancho_tablero)) {
cadena = tablero.cuadro[posicion];
/*check that in each column there are occurrences of the same figure
'X' or 'O' */
for (i = (posicion + ancho_tablero); i < numero_de_cuadros; i +=
ancho_tablero)
cadena = cadena & tablero.cuadro;
ganador = (cadena != vacio) ? cierto : falso;
posicion++;
} /* end while - check columns */
/* check diagonals */
/* diagonal from left upper corner */
if (ganador==falso) {
cadena = tablero.cuadro[0];
for (i = (ancho_tablero + 1); i < numero_de_cuadros; i +=
(ancho_tablero + 1))
cadena = cadena & tablero.cuadro;
ganador = (cadena != vacio) ? cierto : falso;
}
/* diagonal from right upper corner */
if (ganador==falso) {
cadena = tablero.cuadro[ancho_tablero - 1];
for (i = (2 * ancho_tablero - 2); i < (numero_de_cuadros - 1);
i += (ancho_tablero - 1))
cadena = cadena & tablero.cuadro;
ganador = (cadena != vacio) ? cierto : falso;
} /* end if */
return ganador;
}
/* fin hay ganador */
/* Function Alpha Beta for Computer Player*/
int alfabeta_computador (tipo_tablero tablero,contenido_del_cuadro
figura_activa,
estado_del_juego *estadox,estado_del_juego alfa,estado_del_juego beta)
{
int i, mejor_jugada;
estado_del_juego turno_actual;
if (hay_ganador (tablero)==cierto)
{
/* The human win with the last play */
*estadox = pierde;
}
else
{
if (esta_lleno_el_tablero(tablero)==cierto)
{
/* the game is over */
*estadox = empata;
}
else
{
/* here it begins the recursive search */
*estadox = alfa;
for (i = 0; (i < numero_de_cuadros) && (*estadox < beta); i++)
{
if (tablero.cuadro == vacio)
{
marcar_el_tablero (&tablero, i, figura_activa);
alfabeta_humano (tablero, ((figura_activa == X) ? O : X),
&turno_actual, *estadox, beta);
borrar_figura (&tablero, i);
if (turno_actual > *estadox)
{
/* found a better move for a player */
*estadox = turno_actual;
mejor_jugada = i;
}
}
}
}
}
return mejor_jugada;
}
/* end of alfabeta computador*/
/* Function Alpha Beta Human*/
void alfabeta_humano (tipo_tablero tablero,
contenido_del_cuadro figura_activa, estado_del_juego *estadox,
estado_del_juego alfa,estado_del_juego beta)
{
int i, auxiliar;
contenido_del_cuadro turno_actual;
if (hay_ganador (tablero)==cierto) {
/* goal state amd terminal case, player has won by last move */
*estadox = gana;
}
else {
if (esta_lleno_el_tablero (tablero)==cierto) {
/* terminal case */
*estadox = empata;
}
else {
/* recursive search */
*estadox = beta;
for (i = 0; (i < numero_de_cuadros) && (*estadox > alfa) ; i++) {
if (tablero.cuadro == vacio) {
marcar_el_tablero (&tablero, i,figura_activa);
auxiliar = alfabeta_computador (tablero, ((figura_activa == X)
? O : X),
&turno_actual, alfa, *estadox);
borrar_figura (&tablero, i);
if (turno_actual < *estadox) {
*estadox = turno_actual;
}
}
}
}
}
}
/* fin alfabeta_humano */
/*Function Clear Figure*/
void borrar_figura (tipo_tablero * tablero, int lugar)
{
if (tablero->cuadro[lugar] != vacio) {
tablero->cuadro[lugar] =vacio;
--(tablero->cuadros_ocupados);
} /* end if */
}
/* end of borrar figura*/
void pulsar_tecla_para_continuar(void)
{
printf("\nPress any key to continue\n");
getch();
}
/* Fuction Minimax for Computer Player*/
int minimax_computador (tipo_tablero tablero,contenido_del_cuadro
figura_activa,
estado_del_juego *estadox,estado_del_juego li,estado_del_juego ls)
{
int i, mejor_jugada;
estado_del_juego turno_actual;
if (hay_ganador (tablero)==cierto) {
*estadox = pierde;
}
else {
if (esta_lleno_el_tablero(tablero)==cierto) {
*estadox = empata;
}
else {
*estadox=li;
for (i = 0; i< numero_de_cuadros ; i++) {
if (tablero.cuadro == vacio) {
marcar_el_tablero (&tablero, i, figura_activa);
minimax_humano (tablero, ((figura_activa == X) ? O : X),
&turno_actual,*estadox, ls);
borrar_figura (&tablero, i);
if (turno_actual > *estadox) {
*estadox = turno_actual;
mejor_jugada = i;
}
}
}
}
}
return mejor_jugada;
}
/*fin minimax computador*/
/*Function Minimax for Human Player*/
void minimax_humano (tipo_tablero tablero,
contenido_del_cuadro figura_activa, estado_del_juego
*estadox,estado_del_juego li,estado_del_juego ls)
{
int i, auxiliar;
contenido_del_cuadro turno_actual;
if (hay_ganador (tablero)==cierto) {
/* goal state amd terminal case, player has won by last move */
*estadox = gana;
}
else {
if (esta_lleno_el_tablero (tablero)==cierto) {
/* terminal case */
*estadox = empata;
}
else {
/*
recursive search
*/
*estadox=ls;
for (i = 0; i < numero_de_cuadros ; i++)
{
if (tablero.cuadro == vacio)
{
marcar_el_tablero (&tablero, i,figura_activa);
auxiliar = minimax_computador (tablero, ((figura_activa == X)
? O : X),
&turno_actual,li,*estadox);
borrar_figura (&tablero, i);
if (turno_actual < *estadox)
{
*estadox = turno_actual;
}
}
}
}
}
}
/* end of minimax_humano */
**********************My Code End Here**************************