/*
* TICTAC.C
*
* Copyright (C) 1990 by Aaron L. Brenner
*
* A game of Tic-Tac-Toe that learns as it goes along.
* The knowledge is stored as a linked list of board configurations (see
* BOARDLIST definition below), each of which points to a linked list of
* move/weight pairs (see PLAYLIST definition below).
*
* Revision history:
* 1.00 06/12/90 ALB Created.
*/
#include <stdio.h>
#include <limits.h>
#include <malloc.h>
#include "tictac.h"
#define mem_err(x) err_exit("memory allocation", x)
#define eof_err(x) err_exit("unexpected EOF", x)
#define write_err(x) err_exit("file write", x)
char memory_name[78] = "tictac.mem"; /* File name for "memory" */
/*
* Define the structure of each recorded move
*/
typedef struct playlist {
unsigned char pl_move; /* Move this corresponds to */
char pl_weight; /* "Weight" for this move */
struct playlist *pl_next; /* Next one in the list */
} PLAYLIST;
/*
* Define the structure of each "remembered" board
*/
typedef struct boardlist {
/* unsigned char bl_board[9]; /* The board positions */
unsigned int bl_board; /* Encoded game board */
unsigned char bl_count; /* Count of play list elements */
PLAYLIST *bl_plays; /* List of plays made here */
struct boardlist *bl_next; /* Next board in the list */
} BOARDLIST;
BOARDLIST *board_memory = NULL; /* Head of list of boards */
PLAYLIST *game_moves[9]; /* Moves we made this game */
int move_count; /* Count of elements in above */
int have_mouse; /* Set during initialization */
unsigned char play_board[9]; /* Current game board */
char *prompt, /* Set at init, depending on */
*yes_no_prompt; /* presence of mouse */
char bad_move[] = "Invalid move";
unsigned games_played = 0,
games_won = 0,
games_lost = 0,
games_drawn = 0;
/*
* This array serves 2 purpose:
* 1. Determine whether or not the mouse cursor is in a square when clicked.
* 2. Identify where to put the markers on screen.
*
* Since this is also used for the mouse, all the screen coordinates are
* 0-based.
*/
REGION screen_regions[] = {
{14, 20, 18, 31},
{14, 34, 18, 45},
{14, 48, 18, 59},
{ 8, 20, 12, 31},
{ 8, 34, 12, 45},
{ 8, 48, 12, 59},
{ 2, 20, 6, 31},
{ 2, 34, 6, 45},
{ 2, 48, 6, 59}
};
#define NUM_REGIONS (sizeof(screen_regions) / sizeof(REGION))
/*
* These arrays define how the markers look.
*
* 0 means space
* 1 means lower-half block
* 2 means upper-half block
* 3 means full block
*/
char omarker[32] = {
0, 1, 1, 1, 1, 1, 1, 0, 3, 0, 0, 0, 0, 0, 0, 3,
3, 0, 0, 0, 0, 0, 0, 3, 2, 1, 1, 1, 1, 1, 1, 2
};
char xmarker[32] = {
0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 2, 1, 0, 1, 2, 0,
0, 0, 0, 1, 2, 1, 0, 0, 0, 1, 2, 0, 0, 0, 2, 1
};
/*
* Error exit routine
*/
void err_exit(char *msg, char *locus)
{
cls(); /* Clear the screen */
fputs("Fatal ", stderr); /* Tell them it's a fatal error */
fputs(msg, stderr); /* Spit out the message */
fputs(" error in/about ", stderr); /* Say about where it is */
fputs(locus, stderr);
fputc('\n', stderr); /* New line */
exit(1); /* Get the hell out of Dodge */
}
/*
* Load any remembered boards from disk
*
* The memory file is organized as follows:
* word count of boards
* <boards>
* <move/weight pairs>
* The count of pairs for each board is stored with the board.
*/
void load_boards()
{
FILE *memfile;
unsigned bcount,
pcount,
count2;
BOARDLIST *tboards, /* Ptr for allocating */
*tbdtail; /* Keeps track of the end of */
/* the board list so we don't */
/* have to chain through the */
/* entire list each time */
PLAYLIST *tplays, /* Ptr for allocating */
*tplaystail; /* Same purpose as tbdtail, but */
/* for the move list */
/*
* Try to open the memory file. If it fails, no big deal, just no memory
*/
if ((memfile = fopen(memory_name, "rb")) != NULL) {
/*
* Make the file buffer bigger than 1 sector so that the I/O goes
* faster
*/
setvbuf(memfile, NULL, _IOFBF, 8192);
/*
* Read in the count of boards. If that fails, die.
*/
if ((bcount = (unsigned)getw(memfile)) == EOF)
eof_err("load_boards[board count]");
tbdtail = NULL; /* Set up the tail ptr */
/*
* Load in each board in the file
*/
for (count2 = 0; count2 < bcount; count2++) {
/*
* Allocate a structure for this board. If it fails, die.
*/
if ((tboards = malloc(sizeof(BOARDLIST))) == NULL)
mem_err("load_boards[board list]");
if (tbdtail == NULL) /* If none yet, */
board_memory = tboards; /* Set the list head */
else /* But if we already have some, */
tbdtail->bl_next = tboards; /* set our tail ptr's ptr */
tbdtail = tboards; /* Point to the last one */
tboards->bl_plays = NULL; /* Set up ptr to play list */
tboards->bl_next = NULL; /* Keep list terminated */
/*
* Read in the board itself. If it fails, die.
*/
if (fread(&(tboards->bl_board), 1, sizeof(tboards->bl_board) +
sizeof(char), memfile) != (sizeof(tboards->bl_board) +
sizeof(char)))
eof_err("load_boards[board data]");
}
/*
* We've read in all the board configurations. Now, we have to go
* through each board, reading in the plays for that board.
*/
for (tboards = board_memory; tboards != NULL;
tboards = tboards->bl_next) {
tplaystail = NULL; /* Set up list tail ptr */
pcount = tboards->bl_count; /* Get play list count */
for (count2 = 0; count2 < pcount; count2++) {
if ((tplays = malloc(sizeof(PLAYLIST))) == NULL)
mem_err("load_boards[play list]");
if (tplaystail == NULL) /* If none yet, */
tboards->bl_plays = tplays; /* Set ptr in board entry */
else /* Otherwise keep list right */
tplaystail->pl_next = tplays;
tplaystail = tplays;
tplays->pl_next = NULL; /* Keep list terminated */
/*
* Read in a move/weight pair. If it fails, die.
*/
if (fread(&(tplays->pl_move), 1, sizeof(unsigned char) +
sizeof(char), memfile) < (sizeof(unsigned char) +
sizeof(char)))
eof_err("load_boards[play list]");
}
}
fclose(memfile); /* Close it */
}
}
/*
* One-time-only program initialization.
* * Draw the main board
* * Initialize the mouse
* * Load the memory file
*/
void initialize()
{
int i;
init_screen(); /* Init the screen package */
set_cursor(OFF); /* Get rid of that sucker */
gotoxy(2, 20); /* Draw the frame */
out_char(0xc9);
for (i = 21; i < 61; i++)
out_char(0xcd);
out_char(0xbb);
for (i = 3; i < 20; i++) {
gotoxy(i, 20);
out_char(0xba);
gotoxy(i, 33);
out_char(0xdb);
out_char(0xdb);
gotoxy(i, 47);
out_char(0xdb);
out_char(0xdb);
gotoxy(i, 61);
out_char(0xba);
}
gotoxy(20, 20);
out_char(0xc8);
for (i = 21; i < 61; i++)
out_char(0xcd);
out_char(0xbc);
gotoxy(8, 21);
for (i = 21; i < 61; i++)
out_char(0xdb);
gotoxy(14, 21);
for (i = 21; i < 61; i++)
out_char(0xdb);
have_mouse = (mouse_init() != 0); /* Hook the mouse */
if (have_mouse) {
mouse_bounds(2, 20, 18, 59);
prompt =
"Select your move by typing a digit from 1 to 9, or by clicking";
yes_no_prompt = "[Y or left button, N or right button]";
} else {
prompt = "Enter your move by typing a digit from 1 to 9";
yes_no_prompt = "[Y or N]";
}
mouse_on(); /* Enable mouse processing */
mouse_cursor(OFF); /* Turn it off */
load_boards(); /* Load the boards from disk */
}
/*
* Set up the board for a new game
*/
void init_board()
{
int i;
move_count = 0; /* Reset game move counter */
memset(play_board, 0, sizeof(play_board)); /* Clear the game board */
/*
* Go through each square in the board (on screen), and clear it.
*/
for (i = 0; i < NUM_REGIONS; i++) {
clear_region(screen_regions[i].ul_row+1, screen_regions[i].ul_col+1,
screen_regions[i].lr_row+1, screen_regions[i].lr_col+1);
gotoxy(screen_regions[i].lr_row + 1, screen_regions[i].lr_col + 1);
intensity(ON);
out_char(i + '1');
intensity(OFF);
}
gotoxy(24, 1);
clear_below();
}
/*
* Display a move
* who is either 1 (for the player) or 2 (for the computer)
* where is a square number (0 to 8)
*/
void show_move(int who, int where)
{
int base_row,
base_col,
t_row,
t_col;
char *temp;
if (who == 1) /* Figure out which marker */
temp = xmarker;
else
temp = omarker;
/*
* Get the base row and column from the region array. Adjust them, since
* they're 0-based in the array and the screen package expects 1-based
* coordinates.
*/
base_row = screen_regions[where].ul_row + 1;
base_col = screen_regions[where].ul_col + 2;
for (t_row = 0; t_row < 4; t_row++) {
gotoxy(base_row + t_row, base_col);
for (t_col = 0; t_col < 8; t_col++, temp++)
switch (*temp) {
case 0: /* Space */
out_char(' ');
break;
case 1: /* Lower half-block */
out_char(0xdc);
break;
case 2: /* Upper half-block */
out_char(0xdf);
break;
default: /* Full block */
out_char(0xdb);
}
}
}
/*
* Get a move from the player
* Returns 1 if they want to quit; 0 otherwise.
*/
int player_move()
{
int oldf,
oldb,
oldi,
oldk,
old_state,
move;
unsigned pinput;
do {
/*
* Clear the last line, and write out the prompt in reverse video
*/
gotoxy(25, 1);
clear_eol();
gotoxy(25, 40 - (strlen(prompt) / 2));
get_attrib(&oldf, &oldb, &oldi, &oldk);
foreground(oldb);
background(oldf);
out_string(prompt);
foreground(oldf);
background(oldb);
if (have_mouse) { /* Turn the mouse cursor on if */
mouse_cursor(ON); /* there is a mouse, and get */
old_state = mouse_buttons(); /* the current button state */
} else
old_state = 0; /* No mouse, so use 0 for start */
/*
* Loop, waiting for either a keystroke or a mouse button click (the
* button goes down then up).
*/
for (;;) {
/*
* See if there are any keystrokes to read.
*/
if ((pinput = tvinkey("1-9^[", "", 0xffff)) != 0xffff) {
if (pinput == 27) { /* Esc quits */
mouse_cursor(OFF);
return (1);
}
move = pinput - '1';
break;
}
/*
* Check the mouse buttons. If they've changed AND the new state
* indicates that a button has gone UP, it means it's been
* clicked. Handle it.
*/
if ((pinput = mouse_buttons()) != old_state) {
if ((old_state & 2) && !(pinput & 2)) {
mouse_cursor(OFF); /* Right button quits */
return (1);
}
if ((old_state & 1) && !(pinput & 1)) {
if ((move = mouse_in_region(screen_regions, NUM_REGIONS))
!= -1)
break; /* Left button selects a square */
}
old_state = pinput; /* Save that as the old state */
}
}
mouse_cursor(OFF); /* Turn the mouse cursor off */
if (play_board[move]) { /* If they picked one that is */
/* already occupied,... */
gotoxy(24, 40 - (strlen(bad_move) / 2));
foreground(oldb);
background(oldf);
out_string(bad_move); /* ..., complain about it */
foreground(oldf);
background(oldb);
} else {
gotoxy(24, 1); /* Erase any message that might */
clear_eol(); /* have been displayed earlier */
}
} while (play_board[move]); /* Loop until they select a */
/* square that isn't occupied */
play_board[move] = 1; /* Mark it as now occupied */
show_move(1, move); /* Show their marker */
return (0);
}
/*
* Indicate what the winning positions are by making them blink
*/
void flash_winner(int index1, int index2, int index3)
{
blinking(ON);
show_move(play_board[index1], index1);
show_move(play_board[index2], index2);
show_move(play_board[index3], index3);
blinking(OFF);
}
/*
* See if the game is finished. If not, return 0. If it is, return 1 if the
* player won, or 2 if the machine won. If it's a draw, return 3.
*/
int game_over()
{
int i;
/*
* The brute force approach is used. Since the board is so small, just
* check for each possible winning combo.
*/
/*
* First, check the diagonals
*/
if (play_board[0] && (play_board[0] == play_board[4]) &&
(play_board[0] == play_board[8])) {
flash_winner(0, 4, 8);
return (play_board[0]);
}
if (play_board[2] && (play_board[2] == play_board[4]) &&
(play_board[2] == play_board[6])) {
flash_winner(2, 4, 6);
return (play_board[2]);
}
/*
* Now, check along each row.
*/
if (play_board[0] && (play_board[0] == play_board[1]) &&
(play_board[0] == play_board[2])) {
flash_winner(0, 1, 2);
return (play_board[0]);
}
if (play_board[3] && (play_board[3] == play_board[4]) &&
(play_board[3] == play_board[5])) {
flash_winner(3, 4, 5);
return (play_board[3]);
}
if (play_board[6] && (play_board[6] == play_board[7]) &&
(play_board[6] == play_board[8])) {
flash_winner(6, 7, 8);
return (play_board[6]);
}
/*
* Lastly, check along the columns.
*/
if (play_board[0] && (play_board[0] == play_board[3]) &&
(play_board[0] == play_board[6])) {
flash_winner(0, 3, 6);
return (play_board[0]);
}
if (play_board[1] && (play_board[1] == play_board[4]) &&
(play_board[1] == play_board[7])) {
flash_winner(1, 4, 7);
return (play_board[1]);
}
if (play_board[2] && (play_board[2] == play_board[5]) &&
(play_board[2] == play_board[8])) {
flash_winner(2, 5, 8);
return (play_board[2]);
}
/*
* Ok, so nobody has won yet. Now check for a draw.
*/
for (i = 0; i < 9; i++)
if (play_board[i] == 0) /* If at least 1 empty space, */
return (0); /* no draw yet */
return (3); /* Return that it's a draw */
}
/*
* Find a possible move, given the position.
*/
PLAYLIST *get_possible(int where)
{
unsigned coded_board; /* Encoded game board */
int i;
BOARDLIST *btemp1,
*btemp2;
PLAYLIST *ptemp1,
*ptemp2;
static unsigned powers[9] = {
3, 9, 27, 81, 243, 729, 2187, 6561, 19683
};
btemp2 = NULL;
/*
* Encode the game board for comparison & storage
*/
coded_board = 0;
for (i = 0; i < 9; i++)
coded_board += powers[i] * (unsigned)play_board[i];
/*
* Search down the list of "remembered" boards, looking for one that
* matches the current game board.
*/
for (btemp1 = board_memory; btemp1 != NULL; btemp1 = btemp1->bl_next) {
/* if (memcmp(btemp1->bl_board, play_board, 9) == 0)
*/ if (btemp1->bl_board == coded_board)
break;
btemp2 = btemp1;
}
if (btemp1 == NULL) {
/*
* We don't have a record of this board configuration, so we need to
* add it to the list (that's what btemp2 is for - so we don't have
* to search for the end again).
*/
if ((btemp1 = malloc(sizeof(BOARDLIST))) == NULL)
mem_err("get_possible[board list]");
if (btemp2 == NULL) /* If the list was empty, */
board_memory = btemp1; /* Make this the head */
else /* Otherwise, */
btemp2->bl_next = btemp1; /* Just tack it onto the end */
btemp1->bl_count = 0; /* Initialize this one */
btemp1->bl_plays = NULL;
btemp1->bl_next = NULL;
/* memcpy(btemp1->bl_board, play_board, 9);
*/ btemp1->bl_board = coded_board; /* Store the encoded game board */
}
/*
* At this point, we've either found the correct board, or we've added it
* to the list. In either case, we now have btemp1 pointing to it. Now,
* all we have to do is zip along the associated playlist until we either
* find this move (in which case we return the pointer to it) or we run
* out of list (so we have to allocate a new one).
*/
ptemp2 = NULL;
for (ptemp1 = btemp1->bl_plays; ptemp1 != NULL; ptemp1 = ptemp1->pl_next) {
if (ptemp1->pl_move == where)
break;
ptemp2 = ptemp1;
}
if (ptemp1 == NULL) { /* This move isn't in the list */
if ((ptemp1 = malloc(sizeof(PLAYLIST))) == NULL)
mem_err("get_possible[play list]");
if (ptemp2 == NULL) /* No head of list yet, so */
btemp1->bl_plays = ptemp1; /* Make it the head */
else
ptemp2->pl_next = ptemp1; /* Just tack it onto the end */
ptemp1->pl_next = NULL; /* Init the new element */
ptemp1->pl_weight = 0;
ptemp1->pl_move = where;
btemp1->bl_count++;
}
return (ptemp1); /* Return whatever element */
}
/*
* Generate a move for the "O"s.
*/
void machine_move()
{
int i,
best_move;
char best_weight;
PLAYLIST *possibles[9]; /* Possible plays */
for (i = 0; i < 9; i++)
if (play_board[i] == 0) /* If this spot is open, */
possibles[i] = get_possible(i); /* Get a possible for it */
else /* If, however, it ain't open, */
possibles[i] = NULL; /* Don't keep a possible for it */
/*
* Go through the possibilities, looking for the highest weight.
*/
best_weight = SCHAR_MIN; /* Start with an outrageous one */
for (i = 0; i < 9; i++)
if ((possibles[i] != NULL) &&
(possibles[i]->pl_weight > best_weight)) {
best_weight = possibles[i]->pl_weight;
best_move = i;
}
play_board[best_move] = 2;
game_moves[move_count] = possibles[best_move];
move_count++;
show_move(2, best_move);
}
/*
* Ask the player if they want to do it again. If so, return 1.
* If there's a mouse, the right button means "No" and the left means "Yes".
*/
int play_again()
{
int oldf,
oldb,
oldi,
oldk,
old_state;
unsigned pinput;
if (have_mouse)
old_state = mouse_buttons();
else
old_state = 0;
gotoxy(25, 1);
clear_eol();
get_attrib(&oldf, &oldb, &oldi, &oldk);
foreground(oldb);
background(oldf);
gotoxy(25, 34 - (strlen(yes_no_prompt) / 2));
out_string("Play again "); /* Ask the question */
out_string(yes_no_prompt);
out_string(" ?");
foreground(oldf);
background(oldb);
/*
* Wait for either a keypress or mouse click.
*/
for (;;) {
if ((pinput = tvinkey("YyNn", "", 0xffff)) != 0xffff)
return ((pinput == 'Y') || (pinput == 'y'));
if ((pinput = mouse_buttons()) != old_state) {
if ((old_state & 2) && !(pinput & 2))
return (0);
if ((old_state & 1) && !(pinput & 1))
return (1);
old_state = pinput;
}
}
}
/*
* Register a win/draw - all weights for the moves are increased by 1 for a
* draw, 2 for a win.
*/
void register_win(int howmuch)
{
int i;
for (i = 0; i < move_count; i++)
if (game_moves[i]->pl_weight <= (SCHAR_MAX - howmuch))
game_moves[i]->pl_weight += howmuch;
}
/*
* Register a loss - all weights for the moves are decreased by 2
*/
void register_loss()
{
int i;
for (i = 0; i < move_count; i++)
if (game_moves[i]->pl_weight > (SCHAR_MIN + 2))
game_moves[i]->pl_weight -= 2;
}
/*
* Display the current game stats (# played, won, lost, and drawn)
*/
void show_stats()
{
int oldf,
oldb,
oldi,
oldk;
char t[6];
/*
* Do the legends in reverse video
*/
get_attrib(&oldf, &oldb, &oldi, &oldk);
foreground(oldb);
background(oldf);
gotoxy(2, 1);
out_string("Played:");
gotoxy(4, 1);
out_string("Won:");
gotoxy(6, 1);
out_string("Lost:");
gotoxy(8, 1);
out_string("Drawn:");
games_played++;
foreground(oldf);
background(oldb);
/*
* Now, display the numbers
*/
gotoxy(2, 10);
out_string(int_asc(t, games_played, 10));
gotoxy(4, 10);
out_string(int_asc(t, games_won, 10));
gotoxy(6, 10);
out_string(int_asc(t, games_lost, 10));
gotoxy(8, 10);
out_string(int_asc(t, games_drawn, 10));
}
/*
* Play the game
*/
void play_game()
{
int machine_first,
winner,
oldf,
oldb,
oldi,
oldk;
machine_first = 0;
get_attrib(&oldf, &oldb, &oldi, &oldk);
do {
init_board(); /* Set up the board */
winner = 0;
if (machine_first)
machine_move();
do {
if (player_move()) /* Get move from the human */
break; /* Exit if they quit */
if (winner = game_over()) /* If the game is over now, */
break; /* then stop */
machine_move(); /* Get a move from the machine */
} while (!(winner = game_over()));/* Play until it's done */
switch (winner) {
case 0: /* They quit */
break; /* Do nothing */
case 1: /* Human won */
gotoxy(24, 36);
foreground(oldb);
background(oldf);
out_string("You won!");
foreground(oldf);
background(oldb);
register_loss();
games_won++;
break;
case 2:
gotoxy(24, 37);
foreground(oldb);
background(oldf);
out_string("I won!");
foreground(oldf);
background(oldb);
register_win(2);
games_lost++;
break;
default:
gotoxy(24, 38);
foreground(oldb);
background(oldf);
out_string("Draw");
foreground(oldf);
background(oldb);
register_win(1);
games_drawn++;
}
/*
* If they didn't quit, let the other one go first next time through
*/
if (winner != 0)
machine_first = (machine_first == 0);
show_stats();
} while (play_again());
}
/*
* Clean up before exiting.
* Save to the memory file, clear the screen, and restore the cursor.
*/
void terminate()
{
FILE *memfile;
BOARDLIST *tboard;
PLAYLIST *tplay;
unsigned bcount,
count;
/*
* Try to create the memory file. If it fails, just die.
*/
if ((memfile = fopen(memory_name, "wb")) == NULL)
err_exit("file creation", "terminate[create memory file]");
setvbuf(memfile, NULL, _IOFBF, 8192);
/*
* Walk the list of boards just to get a count.
*/
for (bcount = 0, tboard = board_memory; tboard != NULL; tboard = tboard->bl_next)
bcount++;
/*
* Save that count to the memory files. If it fails, (you guessed it) die.
*/
if (putw(bcount, memfile) == EOF)
write_err("terminate[board count]");
/*
* Now, walk the list to write each board out.
*/
for (tboard = board_memory; tboard != NULL; tboard = tboard->bl_next)
if (fwrite(&(tboard->bl_board), 1, sizeof(tboard->bl_board) +
sizeof(char), memfile) !=
(sizeof(tboard->bl_board) + sizeof(char)))
write_err("terminate[board list]");
/*
* Lastly, walk the board list to write out the move lists for each one.
*/
for (tboard = board_memory; tboard != NULL; tboard = tboard->bl_next) {
for (tplay = tboard->bl_plays; tplay != NULL; tplay = tplay->pl_next)
if (fwrite(&(tplay->pl_move), 1, sizeof(unsigned char) +
sizeof(char), memfile) !=
(sizeof(unsigned char) + sizeof(char)))
write_err("terminate[play list]");
}
fclose(memfile);
cls();
set_cursor(ON);
}
/*
* Main logic.
*/
main()
{
initialize(); /* Set everything up */
play_game(); /* Play the game */
terminate(); /* Clean up before exiting */
return (0); /* Exit code of 0 */
}
