|
25 Years of Programming
An open source source for C, C++, OWL, BASIC, MDB, XLS, DOT, and more... |
Home Projects Up Sitemap Search Blog Forum+Chat About Us Privacy Terms of Use Feedback FAQ Images Services Ads Donate Humor |
|
|
Tic Tac Toe Borland C++ MSDOS console game program learns from experienceTictac.cpp plays the game of Tic-Tac-Toe (XO) against itself or the user. It knows nothing about strategy, only the rules. It scores game outcomes by whether it won or lost, and how quickly. In subsequent games, it chooses moves that are likely to repeat good results, avoid bad ones, or do both with the same move, if it can. Over time, it learns what works and what doesn't, and its playing ability improves. Written using the Borland C++ 4.0 (Windows 3.1) IDE, it is an MSDOS-target console application in which all input and output is textual. It uses the Borland BIDS container classes TArrayAsVector (direct array) and TIArrayAsVector (indirect array). Included in the free tictactoe.zip download (203 KB) are
The Excel and Word files should be renamed after you've unzipped them and chosen the version you want to use. Microsoft Visual C++ versionAlso available is a version of the program that has already been converted to Microsoft Visual C++ with .NET CLR and STL. It will compile with Visual C++ Express Edition, which is available free at the Microsoft website. The cost of the converted TicTacToe.cpp is US$5.00. The reason you might want it is that it saves you the time required to do the conversion yourself, which I found took about 3 hours. The zip file contains:
The button below goes to the PayPal website. After processing your payment, PayPal should redirect you to our download page. If you cancel out of the transaction at PayPal (with their Return to... link), they will direct you back to this page instead of the download page. If you encounter any problem with the payment and download procedure, please tell us. TicTacToe.cpp is the first item we are offering by this method, so glitches are possible. If any part of the process fails, we can email the file to you. If you can't use PayPal, contact us from our Feedback page. You can use one of the alternative payment methods shown on our Services page, and we can send the file by email. |
/* tictac.cpp 12-25-96
Copyright (C)1996 Steven Whitney.
Published under GNU GPL (General Public License) Version 3, with ABSOLUTELY NO WARRANTY.
Initially published by http://25yearsofprogramming.com.
MSDOS target. It is a console app that uses a constream, and it uses the system()
function in a couple of places to execute DOS command lines.
plays tic tac toe against user or itself. learns from experience.
1996: This is an important project (2006: ...by my standards at the time...)
because it is probably the simplest possible
one to include a rudimentary implementation of each of the
Requirements for Learning from complex.doc.
It is important that the learning routines be as general, and as
generalizable, as possible so that their basis in the "Requirements
for Learning" is clear, and so that anything learned here can be
incorporated there.
to do
maybe rename Player to TicTacToePlayer.
Maybe collapse Human into Player, using a flag for whether it's human, and
if it is, just calling different functions when appropriate.
Goal is to make it as easy as possible to use these in other programs.
But when would you need a human player in any other program? (checkers or chess?)
it does lack the ability to innovate: given a current situation, if there
does exist any achievable future known to it, it will always choose that.
It always finds the best known way, but it can't look for a better way.
Could use a random move occasionally even when there's a known move, but would
be better if it could figure out when a random move might be a good gamble.
When the chosen move doesn't have a high enough score?
However, the random player does innovate with random moves, and if it wins,
that board goes into master, which the computer then refers to.
There also is going to be general score inflation, since scores can only increase.
Should there be a drain, so that long-unused positions fall toward zero
(must never reach zero, which is ties), and become the first to be deleted?
Then, when a move is deleted, it will cause innovation in the form of a
forced random move instead.
determine whether it is possible to determine the "don't care" positions in
the boards in master (see complex.doc).
Write a complete text overview of this program, what it does, how it works,
features it has, what it is supposed to show, how it relates to the
requirements for learning.
when 2 random players play, allow one to have a memory, and save it as masterdb.rnd.
This will eventually approach a complete list of possible legal games.
The learner memory won't. Due to its learning, it simply won't let some boards happen.
it sometimes picks an offensive move, ignoring the defensive move that is required
to prevent opponent winning with next move. Don't do anything yet. It may be
an unavoidable part of its learning.
tabulate position frequencies manually in tictac.xls. determine to what
degree certain positions participate more frequently in high scored boards.
Analyze combinations move by move:
1st move X, 9 possibilities, etc.
5th move X, but ONE of them may be a winner that ends the game.
Results
-------
Masterdb.sav has experience from 76000 learner vs. random games 88/5/6 543
Masterdb.sav 86000 games, after getmostfreqapproach() added 90/3/5 543 (none added)
so the improvement is probably from the addition, not from more experience
after 377000 games 90/3/5 546 (3 added)
after 415000 games 90/3/6 546 (none added)
percents shown are learner/random/ties
learning methods:
0: two random players (baseline), ties=1000 44/44/12
1: save all boards, passback 20%, 26000 games, ties=1000 47/41/12
2: save only end boards, no passback, 33000 games ties=1000 50/38/11 954 in memory
3: same as #2 but ties reward=0, 50000 games, 56/33/10 950
4: markpotentials-related changes fixed something by accident 82/10/6
2 learners go rapidly to 100% tie games
5: same as #4, 52000 games 87/5/6 532
-----
Notes
There are some ideas in this program that should be added as subtopics to the
"Requirements for Learning" in complex.doc. That is, functional steps that
are needed for the implementation of the various major categories.
Would a larger board add any challenge, interest, or anything new for the human?
A really big board could wind up, or maybe be converted to, something like Go.
Also, what about a new game like tic-tac-toe, with an 8x8 board and for any
number of players? If so,
change initializing "---------" to use a #defined variable, so if board size
changes, it can be easily changed. Make all necessary other related changes.
The method used here is probably similar to that used in chess playing programs
that use a look-ahead method. The greatest difficulty of adapting this
program to a more complicated environment will be in the test to determine
whether a particular future can result from the current state. Currently,
it is a simple strand() test, which essentially just determines if the
current state already exists coded within the future state.
Nothing here takes into consideration the possibility of rotating the board
to reduce # of positions. Don't do it unless it promises any applicability
to more general situations.
See tictac.xls for calculations on total number of possible games.
*/
#include <alloc.h> // for farcoreleft
#include <math.h>
#include <graphics.h>
#include <classlib\arrays.h>
#include "c:\bcs\my.h"
#pragma hdrstop
#include "c:\bcs\mylib.cpp"
////////////////////////////////////////////////////////////////////////////
// global data
enum // constants for status markers in master db
{
RESET, // starting status, must be zero
POTENTIAL, // can theoretically result from the current state
APPROACHABLE, // a move by this player can advance toward this future
AVOIDABLE // a move by this player can prevent this future
};
constream scr; // console screen
////////////////////////////////////////////////////////////////////////////
// the TicTacToeBoard keeps track of the board, posts moves (or rejects them),
// can display the board, determines when a game ends, whether a win occurred,
// and keeps statistics on cumulative number of games played, how many games
// each player won, and the players names.
// If player names change, you must construct a new TicTacToeBoard for them.
// positions on the board are
// 012
// 345
// 678
// and are stored in a single string as 012345678
class TicTacToeBoard
{
public:
TicTacToeBoard();
void newgame(const string& xplayer, const string& oplayer); // start a new game
void showboard(const string&); // show board, formatted for user viewing
void showstats(); // show cumulative win/lose/tie statistics
int play(int who,int where); // post a move. who = x/o, where = 0-8
long getplayerstats(const string& who, long& won, long& tied); // for 1 player
string prevboard; // previous board
string board; // current board, 9-char string
BOOL verbose; // whether to give running text account of game
// (not desirable when 2 computers play each other)
protected:
void postwinner(int); // log the result of 1 game
int gameover(); // determine if game ended
int isawinningstring(const string&); // determine if a player won
string who1; // alpha names of the players, and length() is used to
string who2; // determine if play can commence (players registered)
int piece1; // the gamepiece each is playing this game
int piece2;
long who1wins; // cumulative match statistics, all games
long who2wins;
long ties;
long gamecount; // number of games played on this board
int moves; // number of moves in current game
};
//--------------------------------------------------------------------------
// constructor
TicTacToeBoard::TicTacToeBoard()
{
board = prevboard = "---------";
moves = 0;
gamecount = who1wins = who2wins = ties = 0L;
verbose = TRUE;
}
//--------------------------------------------------------------------------
// determines whether the string it is given contains 3 consecutive Xs or Os.
// returns the player who won (x or o), or 0 (zero) if no one did.
int TicTacToeBoard::isawinningstring(const string& t)
{
if((t == "xxx") || (t == "ooo"))
return(t[0]);
return(0);
}
//--------------------------------------------------------------------------
// determine if current game is over
// returns x, o, or t (tie) if game is over, 0 (zero) if game is not over.
int TicTacToeBoard::gameover()
{
int winner;
string t;
// did someone win?
// 3 horizontal ways to win
t = board[0]; t += board[1]; t += board[2];
if(winner = isawinningstring(t))
return(winner);
t = board[3]; t +=board[4]; t +=board[5];
if(winner = isawinningstring(t))
return(winner);
t = board[6]; t +=board[7]; t +=board[8];
if(winner = isawinningstring(t))
return(winner);
// 3 vertical
t = board[0]; t +=board[3]; t +=board[6];
if(winner = isawinningstring(t))
return(winner);
t = board[1]; t +=board[4]; t +=board[7];
if(winner = isawinningstring(t))
return(winner);
t = board[2]; t +=board[5]; t +=board[8];
if(winner = isawinningstring(t))
return(winner);
// 2 diagonal
t = board[0]; t +=board[4]; t +=board[8];
if(winner = isawinningstring(t))
return(winner);
t = board[6]; t +=board[4]; t +=board[2];
if(winner = isawinningstring(t))
return(winner);
// if we get here, no one won.
if(!board.contains("-")) // if there are no blank spaces left,
return('t'); // board is full, for a tie game.
return(0); // no win or tie, game still continuing
} // end gameover
//----------------------------------------------------------------------------
// log the result of a game & update stats
// called by play()
void TicTacToeBoard::postwinner(int winner) // must be x,o,t
{
if(winner <= 0) // allows calling with raw result of gameover()
return; // does nothing if winner isn't valid
// translate the winning piece to the winning player
if(piece1 == 'x') // who1=x who2=o
switch(tolower(winner))
{
case 'x': who1wins++; break;
case 'o': who2wins++; break;
case 't': ties++; break;
}
else // who1=o who2=x
switch(tolower(winner))
{
case 'x': who2wins++; break;
case 'o': who1wins++; break;
case 't': ties++; break;
}
gamecount++;
} // end postwinner
//----------------------------------------------------------------------------
// start a new game: reset board and
// record player names and which piece each is playing (x,o)
// first name plays x, second name plays o
void TicTacToeBoard::newgame(const string& xplayer, const string& oplayer)
{
board = prevboard = "---------"; // reset game board
moves = 0;
// if whos are empty, it's the first entry, so register the players
if(!who1.length() || !who2.length())
{
who1 = xplayer; piece1 = 'x';
who2 = oplayer; piece2 = 'o';
}
else // players already registered
{
if(xplayer == who1) // but they're changing sides
{
piece1 = 'x';
piece2 = 'o';
}
else
{
piece1 = 'o';
piece2 = 'x';
}
}
} // end newgame
//----------------------------------------------------------------------------
// display a string as a tic tac toe game board, formatted for user viewing
// if no string provided, shows the member board.
void TicTacToeBoard::showboard(const string& s = "")
{
string t(s); // copy so toupper doesn't change s
if(t.length() < 9) // empty string means use a copy of member board
t = board;
t.to_upper();
scr << t[0] << " " << t[1] << " " << t[2] << endl;
scr << t[3] << " " << t[4] << " " << t[5] << endl;
scr << t[6] << " " << t[7] << " " << t[8] << endl;
} // end showboard
//----------------------------------------------------------------------------
// show a score box with various statistics
void TicTacToeBoard::showstats()
{
if(gamecount <= 0L) // prevent divide by zero below
return;
scr << gamecount << " games ";
scr << who1 << "=" << who1wins << " ";
scr << who2 << "=" << who2wins << " Ties=" << ties;
scr << ", Percents= ";
scr << (100L * who1wins / gamecount) << " ";
scr << (100L * who2wins / gamecount) << " ";
scr << (100L * ties / gamecount) << endl;
} // showstats
//--------------------------------------------------------------------------
// get performance statistics for 1 player.
// Fills provided variables with stats for the named player.
// Returns gamecount, or 0 if no games or named player not registered.
long TicTacToeBoard::getplayerstats(const string& who, long& won, long& tied)
{
tied = ties;
if(who == who1)
won = who1wins;
else
if(who == who2)
won = who2wins;
else
{
scr << "Error: No stats. Player not registered.\n";
won = tied = 0L;
return(0L);
}
return(gamecount);
} // end getplayerstats
//--------------------------------------------------------------------------
// posts a move from a player
// returns the result of the move:
// -1 move rejected (illegal)
// 0 move accepted, and game not finished
// x x wins
// o o wins
// t tie game
int TicTacToeBoard::play(int who, int where)
{
if(!who1.length() || !who2.length())
{
scr << "Error: Players not registered." << endl;
return(-1); // -1 could cause infinite loops
}
who = tolower(who);
if((who != 'x') && (who != 'o')) // illegal player
return(-1);
if((where < 0) || (where > 8)) // illegal move
return(-1);
if(board[where] != '-') // illegal: space already occupied
return(-1);
if(!board.contains("-")) // illegal: game already over
return(-1);
prevboard = board; // save previous board
board[where] = who; // make the requested new move
moves++; // increment move count
int endflag = gameover(); // did this move end the game?
if(verbose)
{
scr << " " << (char)toupper(who) << " plays " << (where+1) << endl;
showboard(); // show the gameboard after the move
switch(endflag) // report result of the move
{
case -1: scr << " Illegal move." << endl; break;
case 0 : /* scr << endl; */ break;
case 'x': scr << " X wins in " << moves << " moves." << endl; break;
case 'o': scr << " O wins in " << moves << " moves." << endl; break;
case 't': scr << " Tie game in " << moves << " moves." << endl; break;
}
}
postwinner(endflag); // updates match stats only if anybody won or tied
return(endflag);
} // end play()
//----------------------------------------------------------------------------
// end class TicTacToeBoard
////////////////////////////////////////////////////////////////////////////
// a Position is a unit of the player's memory. It consists of a board
// position encountered, and a historical rating of the position, based
// on whether it contributed to wins or losses for 'x' in previous games.
struct Position
{
Position() { score = 0.; status = RESET; }
Position(const string& p, double s = 0.) : pos(p), score(s) { status = RESET; }
Position(const Position& p) : pos(p.pos), score(p.score) { status = RESET; }
BOOL operator == (const Position& other) const { return(pos == other.pos); }
BOOL operator < (const Position& other) const { return(pos < other.pos); }
string pos; // a board position
double score; // its historic desirability, always relative to X
// + means desirable for x, undesirable for o
int status; // a rating of its usefulness in the current game at the present time
string moves; // moves that a Player can actually make to approach/avoid this position
// must be coded so that a xo char is located where you can actually play xo.
};
//----------------------------------------------------------------------------
// end class Position
////////////////////////////////////////////////////////////////////////////
// the computerized tic tac toe player
// it can either learn or play with entirely random moves.
// there may still be some public members that should be protected
class Player
{
public:
Player();
~Player();
void showthisgame(); // display all moves from this game
void showmaster(); // display all scored positions in master
void savemaster(); // save master database to disk
void loadmaster(); // load master database from disk
void gameendtally(int,const TicTacToeBoard&); // game over: assign scores, empty array
void switchsides(string&); // invert x's and o's in a string
int chooseside(); // choose either 'x' or 'o' at random
int takeotherside(int); // assigns opposite gamepiece to this object
int move(TicTacToeBoard&); // make a move
int randommove(TicTacToeBoard&); // make a random move
string name; // this player's alpha name
int xo; // its game piece, x or o
BOOL randomplayer; // if TRUE, it plays only random moves
BOOL showstrategy; // if TRUE, shows its reasoning
protected:
int getcommonmoves(const Position* s, const Position* t, string& result);
int markpotentials(const TicTacToeBoard&); // mark futures that could occur
int markapproachables(const TicTacToeBoard&); // mark futures we can move toward
int markavoidables(const TicTacToeBoard&); // mark futures we can prevent
int getmostfreqapproach(const string&); // choose most useful approach move
int getmostfreqavoid(const string&); // choose most useful avoid move
BOOL howtoapproach(const TicTacToeBoard& current, Position* future);
BOOL howtoavoid(const TicTacToeBoard& current, Position* future);
BOOL cullmaster(int); // delete least useful Position from master
BOOL addtomaster(const Position&); // add a board position into master
Position* getbestfuture(); // find highest scored achievable future
Position* getworstfuture(); // find (lowest) scored preventable future
TArrayAsVector<Position> thisgame; // moves from the game currently in progress
TIArrayAsVector<Position> master; // archive memory of previous board positions
};
//--------------------------------------------------------------------------
// constructor
Player::Player() : thisgame(10,0,1), master(2000,0,10)
{
randomplayer = showstrategy = FALSE;
name = "Comp";
}
//--------------------------------------------------------------------------
// destructor
Player::~Player()
{
master.Flush(TShouldDelete::Delete); // maybe not necessary
}
//--------------------------------------------------------------------------
// take either 'x' or 'o' at random. returns the piece chosen.
int Player::chooseside()
{
xo = (random(2) ? 'x' : 'o');
return(xo);
} // end chooseside
//--------------------------------------------------------------------------
// if the other side has already chosen a side, take the other side.
// returns the resulting (forced) choice.
int Player::takeotherside(int taken)
{
switch(tolower(taken))
{
case 'x': xo = 'o'; break;
case 'o': xo = 'x'; break;
}
return(xo);
} // end takeotherside
//--------------------------------------------------------------------------
// display all moves from this game
void Player::showthisgame()
{
scr << "Moves from the most recent game: " << endl;
int thiscount = thisgame.GetItemsInContainer();
for(int i = 0 ; i < thiscount ; i++)
scr << thisgame[i].pos << " " << thisgame[i].score << endl;
scr << endl;
} // end showthisgame
//--------------------------------------------------------------------------
// display all scored positions in master db
void Player::showmaster()
{
if(randomplayer) // if random, nothing to show
return;
scr << "The scored gameboard positions in memory are: " << endl;
int mastercount = master.GetItemsInContainer();
for(int i = 0 ; i < mastercount ; i++)
{
scr << master[i]->pos << " ";
scr << setw(12) << setprecision(1) << setiosflags(ios::fixed);
scr << master[i]->score << endl;
if(i && !(i % 20))
presskey();
}
scr << endl;
} // end showmaster
//--------------------------------------------------------------------------
// save all scored positions in master db to disk
void Player::savemaster()
{
if(randomplayer) // if random, nothing to save
return;
ofstream outfile("masterdb.dat");
int mastercount = master.GetItemsInContainer();
for(int i = 0 ; i < mastercount ; i++)
outfile << master[i]->pos << " "
<< setw(12) << setprecision(2) << setiosflags(ios::fixed)
<< master[i]->score << endl;
} // end savemaster
//--------------------------------------------------------------------------
// load previously saved scored positions from disk
void Player::loadmaster()
{
if(randomplayer) // if random, don't load
return;
string position;
double score;
ifstream infile("masterdb.dat");
if(!infile)
scr << "File MASTERDB.DAT not found." << endl;
else
while(infile >> position >> score)
addtomaster(Position(position,score));
} // end loadmaster
//--------------------------------------------------------------------------
// delete least useful position(s) from the master db
// least useful has score nearest to zero
// returns TRUE if one was deleted, FALSE if not.
// could change so it deletes all with a score below some threshold.
BOOL Player::cullmaster(int deletecount = 1)
{
if(randomplayer || !master.GetItemsInContainer())// no point if random or empty
return(FALSE);
for(int d = 0 ; d < deletecount ; d++) // delete specified number of elements
{
int index; // index of position to delete
double compare = 1E300; // comparison value
double poscore;
int mastercount = master.GetItemsInContainer();
for(int i = 0 ; i < mastercount ; i++)
{
poscore = fabs(master[i]->score);
if(poscore < compare)
{
compare = poscore;
index = i;
}
}
master.Destroy(index);
}
return(TRUE);
} // end cullmaster
//--------------------------------------------------------------------------
// add a board position to master, and do any associated tabulation.
// Returns TRUE if position was successfully added, FALSE if not.
BOOL Player::addtomaster(const Position& p) // the position to save
{
// keep a minimum amount of free heap
// using while(farcoreleft()) caused mass deletions, down to 300 or so.
// Probably because the array isn't resized with every deleted element?
// at any rate, deleting 1 element should free enough room for a new one.
if(farcoreleft() < 50000UL)
cullmaster();
if(master.Add(new Position(p)))
{
// do any tabulation of the new record here
return(TRUE);
}
scr << "Error: Could not add record to master db." << endl;
return(FALSE);
} // end addtomaster
//--------------------------------------------------------------------------
// after game is over:
// post only the final board position to master database, no passback,
// and empty the thisgame array.
void Player::gameendtally(int whowon, const TicTacToeBoard& b) // x, o, t
{
// a random player doesn't need a memory, and if game empty, nothing to tally
if(randomplayer || !thisgame.GetItemsInContainer())
{
thisgame.Flush(); // empty to prepare for next game
return;
}
// if the last move was the other player's, add the move to record of game
if(thisgame[thisgame.GetItemsInContainer() - 1].pos != b.board)
thisgame.Add(Position(b.board));
int thiscount = thisgame.GetItemsInContainer(); // ok to calc now, after Add()
double endscore;
switch(whowon = tolower(whowon))
{
case 'x': endscore = 100.; break; // values based on what was good for
case 'o': endscore = -100.; break; // 'x', regardless of who had it.
case 't': endscore = 0.; break; // ties neutral, but are the last
} // resort goal just by being there
// bonus for leading to a win quickly, and also to provide greater variety
// in scores given to endgame boards, so they aren't all the same.
endscore /= (double)thiscount;
// last position gets its reward
thisgame[thiscount-1].score = endscore;
// post or update final board position to master database
BOOL posted = FALSE;
int mastercount = master.GetItemsInContainer();
for(int j = 0 ; j < mastercount ; j++)
if(thisgame[thiscount-1].pos == master[j]->pos) // already in db
{
master[j]->score += thisgame[thiscount-1].score; // so add score
posted = TRUE;
break;
}
if(!posted) // wasn't in master db
addtomaster(thisgame[thiscount-1]); // add it
thisgame.Flush(); // empty the thisgame array to prepare for next game
} // end gameendtally
//--------------------------------------------------------------------------
// flip a board position string so all Xs become Os and vice versa.
// all other chars, including '-', are unchanged.
void Player::switchsides(string& p)
{
int length = p.length();
for(int i = 0 ; i < length ; i++)
switch(p[i])
{
case 'x': p[i] = 'o'; break;
case 'o': p[i] = 'x'; break;
}
} // end switchsides
//--------------------------------------------------------------------------
// given two strings containing potential moves, determine how many
// moves are common to both strings (which makes those moves especially good)
// returns the number of common moves, and codes those moves into result string
// The strings (in Position->moves) must contain xo where you plan to play xo.
// The result string contains xo in any position that a common move occurred,
// and a '-' in all other positions.
int Player::getcommonmoves(const Position* s, const Position* t, string& result)
{
int commoncount = 0; // counter
result = "---------"; // default, no common moves
if(s && t) // both pointers must be valid!
{
// min() test is for safety, but they should always be the same length
int count = min(s->moves.length(),t->moves.length());
for(int i = 0 ; i < count ; i++)
if((s->moves[i] == xo) && (t->moves[i] == xo))
{
result[i] = (char)xo;
commoncount++;
}
}
return(commoncount);
} // end getcommonmoves
//--------------------------------------------------------------------------
// determine the moves that can advance TOWARD a specific desirable future
// this function creates a string containing only the additions that YOU can
// make using your current gamepiece (x or o) to current to make it match future.
// Only additions are allowed, because the past can't be changed here.
// returns TRUE if you can play your gamepiece (X or O) to move towards this
// future, and puts the possible moves into the result string,
// returns FALSE and puts no moves in the result string
// if there are no moves available to you.
// example of choosing offensive move (you are x):
// current X-------O can move towards this...
// good future XXXO----O by any of these moves...
// -XXO----- These are the differences.
// -XX------ But, playing x, you can only use one of these,
// so this is what is returned.
// Before calling, you must know that future CAN be derived from current.
BOOL Player::howtoapproach(const TicTacToeBoard& current, Position* future)
{
if(!future) // must be valid
return(FALSE);
future->moves = "---------"; // default means future is impossible from here
if((current.board.length() != future->pos.length()) ||
(current.board.length() != future->moves.length()))
return(FALSE);
// create a string containing moves that current needs to make it match future
// after this pass, the result string contains additions playable by either side
// already-fixed positions are marked with '-' (they're not playable)
// unspecififed positions in the future state are also marked with '-'
int count = current.board.length();
for(int i = 0 ; i < count ; i++)
future->moves[i] = (current.board[i] == '-') ? future->pos[i] : '-';
// now strip out the moves you can't make because they're the other side
count = future->moves.length();
for(i = 0 ; i < count ; i++)
if(future->moves[i] != xo)
future->moves[i] = '-';
// after the stripping, result might not contain any moves you can make
return(future->moves.contains((char)xo));
} // end howtoapproach
//--------------------------------------------------------------------------
// determine moves YOU can make to PREVENT a specific undesirable future.
// returns TRUE and fills the result string with your possible moves
// if you can make a move that prevents this future.
// returns FALSE and result string contains no moves if you can't prevent it.
// example of choosing defensive move (you are X):
// current O-----X-X given this,
// bad future OOO-X-XOX this could result, but can be prevented.
// -XX----X- These are the moves you can choose from.
// Before calling, you must know that future CAN be derived from current.
//
// Not sure this function is as necessary as howtoapproach(), and it could
// be more difficult. Avoiding a particular future is so easy, it seems like
// there should be more attention dedicated to figuring out what about it
// should be avoided. Basically, this version just works like
// howtoapproach(), except at the end it changes all the other player's pieces
// to yours so you can play a piece where your opponent would have played.
BOOL Player::howtoavoid(const TicTacToeBoard& current, Position* future)
{
if(!future) // must be valid
return(FALSE);
future->moves = "---------"; // default contains no moves
if((current.board.length() != future->pos.length()) ||
(current.board.length() != future->moves.length()))
return(FALSE);
// after this pass, the result string contains additions playable by either side
// to achieve this future, same as howtoapproach() <--
int count = current.board.length();
for(int i = 0 ; i < count ; i++)
future->moves[i] = (current.board[i] == '-') ? future->pos[i] : '-';
// since you want to prevent, not achieve, this future,
// strip out your own moves, leaving only your opponent's
count = future->moves.length();
for(i = 0 ; i < count ; i++)
if(future->moves[i] == xo)
future->moves[i] = '-';
switchsides(future->moves); // translate the other side's moves to be your own
// prevent the future by putting your piece where your opponent's piece would go
// to achieve that future. the result string has a xo in all the non-xo
// positions (to steal your opponent's moves), but '-' everywhere else:
// '-' in fixed positions (you can't change them),
// '-' in unspecified positions in the future state (nothing to change)
// '-' in xo positions (don't play your moves that would help achieve it)
// now the string contains your opponent's potential moves that
// you have taken to be your own, and recoded as YOUR moves,
// but there may not have been any.
return(future->moves.contains((char)xo));
} // end howtoavoid
//--------------------------------------------------------------------------
// make a random move
// returns the result of the move, as returned by TicTacToeBoard::play()
int Player::randommove(TicTacToeBoard& b)
{
int where, result;
do
{
where = random(9); // generate a random move, until a valid one results
}
while((result = b.play(xo,where)) == -1); // while the move is illegal
return(result);
} // end randommove
//--------------------------------------------------------------------------
// find and mark futures in master that could result from current situation
// returns the number of futures that were marked
int Player::markpotentials(const TicTacToeBoard& current)
{
int count = 0;
int mastercount = master.GetItemsInContainer();
for(int i = 0 ; i < mastercount ; i++)
{
master[i]->status = RESET; // make sure all start fresh
// if current.board == future, you can't do anything to "achieve" (or prevent) it
if(master[i]->pos != current.board)
if(strand(master[i]->pos,current.board,'-')) // future is possible
{
master[i]->status = POTENTIAL; // mark it
count++;
}
}
return(count);
} // end markpotentials
//--------------------------------------------------------------------------
// mark all the futures in master that we can currently make a move to move toward
// For each marked record, the actual moves you can make are saved
// in the corresponding future's ->moves field in master.
// you must have called markpotentials() immediately before calling this
// The marking overwrites a record's "achievable" marker.
// Could make the field bitmapped.
// Moving the marking into separate functions is less efficient and slower
// than earlier version because more records are run through howtoapproach(),
// but you can now do it anytime you want, and have more flexibility in
// how to use the result, because all relevant records got marked.
// returns the number of marked records
int Player::markapproachables(const TicTacToeBoard& b)
{
int count = 0; // number of records marked
BOOL desirable; // whether a record should be considered for marking
int mastercount = master.GetItemsInContainer();
for(int i = 0 ; i < mastercount ; i++)
{
if(!master[i]->status) // ignore if not marked as achievable
continue;
// >= and <= cause tie game positions to be considered
if(xo == 'x') // computer playing 'x',
desirable = (master[i]->score >= 0.); // consider positive scored futures
else // computer playing 'o',
desirable = (master[i]->score <= 0.); // consider negative scored futures
if(desirable)
if(howtoapproach(b,master[i])) // if result has an xo move in it
{
master[i]->status = APPROACHABLE; // mark it
count++;
}
}
return(count);
} // end markapproachables
//--------------------------------------------------------------------------
// mark all the futures in master that we can currently make a move to prevent
// For each marked record, the actual moves you can make are saved
// in the corresponding future's ->moves field in master.
// you must have called markpotentials() immediately before calling this
// The marking overwrites a record's POTENTIAL marker.
// returns the number of marked records
int Player::markavoidables(const TicTacToeBoard& b)
{
int count = 0; // number of records marked
BOOL undesirable; // whether a record should be considered for marking
int mastercount = master.GetItemsInContainer();
for(int i = 0 ; i < mastercount ; i++)
{
if(!master[i]->status) // ignore if not marked as achievable
continue;
// you don't want to avoid tie game positions
if(xo == 'x') // computer playing 'x',
undesirable = (master[i]->score < 0.); // negative scored futures are bad
else // computer playing 'o',
undesirable = (master[i]->score > 0.); // positive scored futures are bad
if(undesirable)
if(howtoavoid(b,master[i])) // if an xo move can prevent this future
{
master[i]->status = AVOIDABLE; // mark it
count++;
}
}
return(count);
} // end markavoidables
//--------------------------------------------------------------------------
// given a string containing possible moves to choose from,
// determine the specific move that makes possible the greatest NUMBER
// of approachable futures. (i.e. the move that allows the most flexibility
// for subsequent moves). This is the alternative to choosing one randomly.
// When choosing randomly, the player, in trying to achieve a future,
// is equally likely to play a move that, while part of that future, had nothing
// to do with its good score. Assuming that the moves that do contribute to
// the good score are also responsible for the value of other similar boards,
// and because those contributing moves occur in the same locations in all
// the boards, while the other, non-contributing, moves are randomly distributed,
// this strategy should favor choosing a move that is significant to that future.
// This method is essentially supposed to prevent wasting a move on what is
// really a "don't care" position in the future. It would be better to figure
// out what the "don't cares" are, but that is currently beyond the system's
// ability. If the number of Positions in master ever becomes a concern, this
// will, however, be necessary, to summarize & consolidate master contents.
// all master->status flags must be valid.
// movestochoosefrom must be the string containing your final selection of
// possible move choices, all playable on the current gameboard,
// and you MUST know that it does contain at least ONE xo char,
// returns the position of the highest-frequency move
// if two or more positions tie, one is chosen at random
int Player::getmostfreqapproach(const string& movestochoosefrom)
{
int movefreq[9] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 }; // for frequency counts
int moveslength = movestochoosefrom.length();
for(int i = 0 ; i < moveslength ; i++)
{
// only bother to tabulate those positions where a move is possible
if(movestochoosefrom[i] == (char)xo)
{
int mastercount = master.GetItemsInContainer();
for(int j = 0 ; j < mastercount ; j++)
if(master[j]->status == APPROACHABLE) // only if approachable
if(master[j]->moves[i] == (char)xo) // only if chars match
movefreq[i]++;
}
}
int highestfreq = 0; // calc. the most times any position was hit
for(i = 0 ; i < 9 ; i++)
highestfreq = max(highestfreq,movefreq[i]);
do // This will hit a single qualifier,
{ // or select randomly from multiple ones.
i = random(9); // generate random positions
} // until you find one that was
while(movefreq[i] != highestfreq); // hit highestfreq times
return(i);
} // end getmostfreqapproach
//--------------------------------------------------------------------------
// given a string containing possible moves to choose from,
// determine the specific move that prevents the greatest NUMBER
// of avoidable futures. This is the alternative to choosing one randomly.
// When choosing randomly, the player, in trying to prevent a future,
// is equally likely to play a move that does prevent that future, but had nothing
// to do with its undesirability. Assuming that relevant moves occur in
// specific locations, while irrelevant moves are randomly distributed,
// this strategy should favor choosing a move that is significant.
// all master->status flags must be valid.
// returns the position of the highest-frequency move
// ->There is currently no planned use for this function.
// ->with an APPROACHABLE/AVOIDABLE parameter, this could be easily
// collapsed into getmostfreqapproach()
int Player::getmostfreqavoid(const string& movestochoosefrom)
{
int movefreq[9] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 }; // for frequency counts
int moveslength = movestochoosefrom.length();
for(int i = 0 ; i < moveslength ; i++)
{
// only bother to tabulate those positions where a move is possible
if(movestochoosefrom[i] == (char)xo)
{
int mastercount = master.GetItemsInContainer();
for(int j = 0 ; j < mastercount ; j++)
// the test value here is the ONLY difference between this and the above function
if(master[j]->status == AVOIDABLE) // only if avoidable
if(master[j]->moves[i] == (char)xo) // only if chars match
movefreq[i]++;
}
}
int highestfreq = 0; // calc. the most times any position was hit
for(i = 0 ; i < 9 ; i++)
highestfreq = max(highestfreq,movefreq[i]);
do // This will hit a single qualifier,
{ // or select randomly from multiple ones.
i = random(9); // generate random positions
} // until you find one that was
while(movefreq[i] != highestfreq); // hit highestfreq times
return(i);
} // end getmostfreqavoid
//--------------------------------------------------------------------------
// identify highest scored achievable future (best you can hope to achieve)
// all master->status positions must be valid and current.
// Depending on whether you are 'x' or 'o', you could be looking for greatest
// + or - values, so you must use fabs().
// Returns pointer to the selected record in master.
Position* Player::getbestfuture()
{
double value;
double offscore = 0.; // score of the best offensive move found (0 if none)
Position* bestfuture = 0; // final choice of future to try for
int mastercount = master.GetItemsInContainer();
for(int i = 0 ; i < mastercount ; i++)
if(master[i]->status == APPROACHABLE) // an achievable desirable future
{
// because of the >=, tie positions (0) ARE considered.
// If two records have same score, it will use last in master (newest).
value = fabs(master[i]->score);
if(value >= offscore) // highest-scored so far
{
offscore = value; // save the score for comparison
bestfuture = master[i]; // save the future
}
}
return(bestfuture);
} // end getbestfuture
//--------------------------------------------------------------------------
// identify worst preventable potential future in master.
// all master->status positions must be valid and current.
// Depending on whether you are 'x' or 'o', you could be looking for greatest
// + or - values, so you must use fabs().
// Returns pointer to the selected record in master.
Position* Player::getworstfuture()
{
double value;
double defscore = 0.; // score of the best defensive move found (0 if none)
Position* worstfuture = 0; // final choice of the future to avoid
int mastercount = master.GetItemsInContainer();
for(int i = 0 ; i < mastercount ; i++)
if(master[i]->status == AVOIDABLE) // a preventable undesirable future
{
// Ties avoid consideration here because they cannot be marked as avoidable
// If two records have same score, it will use last in master (newest).
value = fabs(master[i]->score);
if(value >= defscore)
{
defscore = value;
worstfuture = master[i];
}
}
return(worstfuture);
} // end getworstfuture
//--------------------------------------------------------------------------
// make a move
// returns the result of the move, as returned by TicTacToeBoard::play()
int Player::move(TicTacToeBoard& b) // the gameboard for this game
{
if(b.board != "---------") // (don't save starting empty board)
thisgame.Add(Position(b.board)); // add opponent's move to record of this game
int result; // result of the move
if(randomplayer) // if this object has been designated a random player,
{ // it always just makes a random move and returns.
result = randommove(b);
thisgame.Add(Position(b.board)); // add resulting board to record of this game
return(result);
}
markpotentials(b); // only achievable futures have any relevance at all
markapproachables(b); // mark all potentially achievable good futures
markavoidables(b); // mark all avoidable bad potential futures
// Now select which future(s) to consider in choosing your move
Position* bestfuture = getbestfuture(); // final choice future to approach
Position* worstfuture = getworstfuture(); // final choice future to avoid
if(showstrategy) // allow computer to display its strategy
{
if(bestfuture)
{
scr << setclr(LIGHTGREEN) << " I am " << (char)toupper(xo)
<< ". I am trying to ACHIEVE (score = "
<< fabs(bestfuture->score) << "):" << endl;
b.showboard(bestfuture->pos);
}
if(worstfuture)
{
scr << setclr(LIGHTRED) << " I am " << (char)toupper(xo)
<< ". I am trying to AVOID (score = "
<< fabs(worstfuture->score) << "):" << endl;
b.showboard(worstfuture->pos);
}
scr << setclr(LIGHTGRAY);
}
// you now have a best possible achievable future, a worst possible preventable
// future, or one or neither. (if either is missing, you have a NULL POINTER)
// Now, you must decide whether you can accomplish both, or must choose one.
string movestochoosefrom; // final list to choose a move from, starts empty
// first choice is to further both offense and defense, if you can.
// otherwise, choose one, based on which is more important (by score)
if(bestfuture && worstfuture) // found both, both pointers valid
{
// forcing the use of the common moves NOW, before determining which
// offensive moves contribute to the good future's good score
// makes it more likely that a non-contributing move will be chosen,
// and defeats the purpose of getmostfreqapproach() later.
string commonmoves; // moves that can accomplish both aims
if(getcommonmoves(bestfuture,worstfuture,commonmoves))
{
movestochoosefrom = commonmoves;
if(showstrategy)
scr << "I can do both." << endl;
}
else // no common moves, must choose one (by magnitude of score)
{
// >= means if scores are the same, use offense
if(fabs(bestfuture->score) >= fabs(worstfuture->score))
movestochoosefrom = bestfuture->moves; // offense
else
movestochoosefrom = worstfuture->moves; // defense
}
}
else // found only one or neither future. ONE or both pointers are null
{
if(bestfuture) // only found best
movestochoosefrom = bestfuture->moves;
if(worstfuture) // only found worst
movestochoosefrom = worstfuture->moves;
} // if both were null, movestochoosefrom is still empty
// If you have a string containing your final move choices, select one to play.
int where = -1; // position to move to (0-8)
if(movestochoosefrom.contains((char)xo)) // if empty, it doesn't, of course
{
// keep this old random section for comparison testing with the new version
// do // this method just chooses one of the possibilities at random
// {
// where = random(9); // generate random positions
// }
// while(movestochoosefrom[where] != xo); // until you hit a marked one
// choose the move that makes possible the greatest number of good futures
where = getmostfreqapproach(movestochoosefrom);
// finally! actually make the move
if((result = b.play(xo,where)) == -1) // -1 test just prevents disaster
where = -1; // couldn't move, force a random one below
}
// all searching failed (e.g. 1st game). last resort is a random move.
if(where == -1)
result = randommove(b);
thisgame.Add(Position(b.board)); // add resulting board to record of this game
return(result);
} // end move
//--------------------------------------------------------------------------
// end class Player
////////////////////////////////////////////////////////////////////////////
// encapsulates the functions required by or for a human player
struct Human
{
Human() { name = "You"; }
void showhelp(); // give game instructions, etc.
int move(TicTacToeBoard&); // get and make a move
int chooseside(); // choose X, O, or Quit
int xo; // the human's gamepiece, X or O
string name; // the human's name
};
//--------------------------------------------------------------------------
// Game instructions and other help
void Human::showhelp()
{
scr << "The Tic-Tac-Toe board consists of 9 spaces." << endl;
scr << "These are numbered:" << endl;
scr << " 1 2 3" << endl;
scr << " 4 5 6" << endl;
scr << " 7 8 9" << endl;
scr << endl;
scr << "You move by entering 1 digit, of the space you wish to move to." << endl;
scr << endl;
} // end showhelp
//--------------------------------------------------------------------------
// allow human to choose X or O (or quit). Returns the choice.
int Human::chooseside()
{
string valid("xoq");
int choice;
do
{
scr << endl << "Do you want X or O (Q to Quit)? ";
choice = tolower(getche());
scr << endl;
}
while(!valid.contains((char)choice));
xo = choice; // note it could be 'q'
return(choice);
} // end chooseside
//--------------------------------------------------------------------------
// get and make human's next move
int Human::move(TicTacToeBoard& b)
{
int where, result;
do
{ // note 1-9 easier to work with than 0-8
scr << "You are " << (char)toupper(xo) << ". Your move (123456789): ";
where = getche() - 0x30; // larger grid will require > 1 digit
scr << endl;
}
while((result = b.play(xo,where-1)) == -1); // while the move is illegal
return(result);
} // end move
//--------------------------------------------------------------------------
// end class Human
////////////////////////////////////////////////////////////////////////////
// global functions
//--------------------------------------------------------------------------
// human plays against computer, which can learn or be random
void humanagainstcomputer()
{
TicTacToeBoard board; // the TicTacToeBoard
Player computer; // the computer Player, learner by default
Human human; // the human player
scr << "\nThe computer can play randomly or learn from experience.\n";
if(yesno("Do you want it to learn from experience",scr))
{
if(yesno("Load computer's memory of previous games from disk",scr))
computer.loadmaster();
}
else
computer.randomplayer = TRUE;
computer.name.prepend(computer.randomplayer ? "R" : "L"); // for displays
if(yesno("Do you want to see the computer's strategy as it plays",scr))
computer.showstrategy = TRUE;
scr << endl << "Please enter your name: ";
cin >> human.name;
scr << endl;
human.showhelp();
while(human.chooseside() != 'q') // human can quit here
{
computer.takeotherside(human.xo); // give computer the other piece
if(human.xo == 'x') // start new game
board.newgame(human.name,computer.name);
else
board.newgame(computer.name,human.name);
board.showboard(); // show starting board
int whowon; // who won this game
while(1) // game continues till someone wins
{
if(human.xo == 'x') // x goes first
{
if(whowon = human.move(board)) // any non-zero means game over
break;
if(whowon = computer.move(board))
break;
}
else
{
if(whowon = computer.move(board))
break;
if(whowon = human.move(board))
break;
}
}
computer.gameendtally(whowon,board); // let computer tally & assess its performance
board.showstats();
} // end while(play more games)
computer.savemaster();
} // end humanagainstcomputer
//--------------------------------------------------------------------------
// two computers play each other. one, neither, or both can be learners.
void twocomputers()
{
TicTacToeBoard board; // the TicTacToeBoard
board.verbose = FALSE;
Player c1, c2; // the computer players, both learners by default
int learnercount;
do
{
scr << "\nDuring play, press ESC to stop.\n\n";
scr << "The computer will play against itself. Do you want...\n";
scr << "1 Two random players.\n";
scr << "2 A random player against a learning player.\n";
scr << "3 Two learning players.\n\n";
scr << "Enter choice: ";
cin >> learnercount;
scr << endl;
}
while((learnercount < 1) || (learnercount > 3));
learnercount--; // count is 1 less than the entry
switch(learnercount) // if only 1 is a learner, it is c2
{ // each player gets a unique name here
case 0: // both random
c1.randomplayer = c2.randomplayer = TRUE;
c1.name.prepend("R"); c1.name += "1";
c2.name.prepend("R"); c2.name += "2";
break;
case 1: // c2 a learner
c1.randomplayer = TRUE;
c1.name.prepend("R");
c2.name.prepend("L");
break;
case 2: // both learners
c1.name.prepend("L"); c1.name += "1";
c2.name.prepend("L"); c2.name += "2";
break;
}
if(learnercount)
{
if(yesno("For learning player(s), load memory of previous games from disk",scr))
{
c1.loadmaster(); // db won't load if it's a random player,
c2.loadmaster(); // so you can just call it for both.
}
scr << endl;
}
int quitflag = FALSE; // for human to stop play
while(!quitflag)
{
c2.takeotherside(c1.chooseside()); // assign game pieces
if(c1.xo == 'x') // start new game
board.newgame(c1.name,c2.name);
else
board.newgame(c2.name,c1.name);
int whowon; // who won this game
while(1) // game continues till someone wins
{
if(c1.xo == 'x') // x goes first
{
if(whowon = c1.move(board)) // any non-zero means game over
break;
if(whowon = c2.move(board))
break;
}
else
{
if(whowon = c2.move(board))
break;
if(whowon = c1.move(board))
break;
}
}
c1.gameendtally(whowon,board); // players tally & assess performance
c2.gameendtally(whowon,board);
board.showstats(); // show the match statistics.
if(kbhit())
{
if(getch() == 27) // ESC stops play
quitflag = TRUE;
}
}
// Must change this when playing 2 different learning methods against each other
c2.savemaster(); // c2 always a learner if either is, and the 2 should be identical
} // end twocomputers
//--------------------------------------------------------------------------
// main
int main(int argc, char** argv)
{
randomize();
string::set_case_sensitive(0);
string::set_paranoid_check(1);
string::initial_capacity(9);
scr.window(1,1,80,25);
scr.clrscr();
scr << setclr(LIGHTGRAY);
scr << "Tic Tac Toe\n";
char ch;
while(1)
{
do
{
scr << endl;
scr << "When the computer plays itself, you see only statistics, not the games.\n";
scr << "Select one of the following:\n\n";
scr << "0 Exit.\n";
scr << "1 You play against the computer.\n";
scr << "2 The computer plays against itself.\n";
scr << "3 View file MASTERDB.DAT, sorted by string\n";
scr << "4 View file MASTERDB.DAT, more or less sorted by score\n";
scr << endl;
scr << "Enter choice: ";
cin >> ch;
scr << endl;
}
while((ch < '0') || (ch > '4'));
switch(ch)
{
case '0':
return(0);
case '1':
humanagainstcomputer();
break;
case '2':
twocomputers();
break;
case '3':
system("sort < masterdb.dat | more");
break;
case '4':
system("sort /r /+10 < masterdb.dat | more");
break;
}
} // end while(1)
} // end main
|
|
|
|