/*
* Ataxx analyzer - think about a chosen set of moves from a given rectangular Ataxx board state.
* Copyright (C) 2004 Mark A. Fitzgerald
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*
* To contact the author, email at mark DOT fitzgerald2 AT sympatico DOT ca.
*/
/*
* This program is not in any way interactive. However, one can set up most any Ataxx board and
* set of moves to investigate -- modify lines 394-400 to do this.
*/
#include
#include
#include
using namespace std;
//Factory.
class Move
{
Move() {}
Move(int srcRow, int srcCol, int destRow, int destCol)
: srcRow(srcRow), srcCol(srcCol), destRow(destRow), destCol(destCol) {}
bool bPass;
bool bInvalidMove;
public:
int srcRow, srcCol, destRow, destCol;
static Move createMove(int srcRow, int srcCol, int destRow, int destCol)
{
Move move(srcRow, srcCol, destRow, destCol);
move.bPass = false; move.bInvalidMove = false;
assert(move.distance() <= 8 && move.distance() != 0); //invalid move
return move;
}
static Move createPass()
{
Move move;
move.bPass = true; move.bInvalidMove = false;
return move;
}
static Move createInvalidMove()
{
Move move;
move.bPass = false; move.bInvalidMove = true;
return move;
}
int distance() {
return (destRow - srcRow) * (destRow - srcRow)
+ (destCol - srcCol) * (destCol - srcCol);
}
bool isGrow() { return (distance() <= 2); }
bool isHop() { return !isGrow(); }
bool isPass() { return bPass; }
bool isInvalid() { return bInvalidMove; }
void printToStdout()
{
if (isPass())
{
cout << "0";
}
else
{
if (isHop())
{
cout << static_cast('a' + srcRow) << (srcCol+1);
}
cout << static_cast('a' + destRow) << (destCol+1);
}
}
};
class MoveSequenceAndScore
{
MoveSequenceAndScore() {}
public:
vector moves;
int score;
static MoveSequenceAndScore scoreWithoutMove(int score)
{
MoveSequenceAndScore mss;
mss.score = score;
return mss;
}
static MoveSequenceAndScore createMSS(Move move, int score)
{
MoveSequenceAndScore mss;
mss.moves.push_back(move);
mss.score = score;
return mss;
}
};
class MoveAndFlippedNbrs
{
private:
bool flippedNbrs[3][3];
public:
Move move;
MoveAndFlippedNbrs(Move move)
: move(move)
{
for (int deltaRow = -1; deltaRow <= 1; ++deltaRow)
for (int deltaCol = -1; deltaCol <= 1; ++deltaCol)
flippedNbrs[deltaRow+1][deltaCol+1] = false;
}
void setFlip(int deltaRow, int deltaCol)
{
flippedNbrs[deltaRow+1][deltaCol+1] = true;
}
bool getFlip(int deltaRow, int deltaCol)
{
return flippedNbrs[deltaRow+1][deltaCol+1];
}
};
//Assumes a two-player game.
class AtaxxGame
{
private:
vector > board;
vector movesAndFlips;
int playerToMove, nRed, nBlue;
int nCols; //precalculated, as it is used very frequently (40% of CPU time to call board[0].size frequently!)).
public:
AtaxxGame(int nRows, int nCols)
{
playerToMove = 1;
assert(nRows > 0 && nCols > 0);
//Create the board.
board.resize(nRows);
for (int iRow = 0; iRow < nRows; ++iRow)
board.at(iRow).resize(nCols);
//Blank the board.
for (int iRow = 0; iRow < nRows; ++iRow)
for (int iCol = 0; iCol < nCols; ++iCol)
board.at(iRow).at(iCol) = 0; //blank
//Set the four corners of the board, and the piece counts.
board.at(0).at(0) = 1; //red
board.at(0).at(nCols-1) = 2; //blue
board.at(nRows-1).at(0) = 2; //blue
board.at(nRows-1).at(nCols-1) = 1; //red
nRed = nBlue = 2;
this->nCols = nCols;
}
int nMovesMade() { return movesAndFlips.size(); }
Move getMoveMade(int iMove) { return movesAndFlips.at(iMove).move; }
int getNRows() { return board.size(); }
int getNCols() { return nCols; }
int getPlayerToMove() { return playerToMove; }
int getTileContents(int iRow, int iCol) { return board[iRow][iCol]; } //.at(iRow).at(iCol); }
int getNRed() { return nRed; }
int getNBlue() { return nBlue; }
int getNBlank() { return (getNRows() * getNCols()) - getNRed() - getNBlue(); }
bool gameIsOver()
{
if (nMovesMade() >= 2)
{
if (getMoveMade(nMovesMade() - 1).isPass()
&& getMoveMade(nMovesMade() - 2).isPass())
{
return true;
}
}
if (getNRed() == 0 || getNBlue() == 0 || getNBlank() == 0)
{
return true;
}
return false;
}
//Make the specified move, flip opposing neighbours of the destination tile, then update
//the player to move.
void makeMove(Move move)
{
MoveAndFlippedNbrs moveAndFlips(move);
int opposingPlayer = (getPlayerToMove()==1)?2:1;
if (move.isPass() == false)
{
//Make the move.
if (move.distance() > 2) {
board.at(move.srcRow).at(move.srcCol) = 0; //clear the source of a 'hop'.
} else {
//It's a 'grow' move.
if (getPlayerToMove() == 1)
++nRed;
else
++nBlue;
}
board.at(move.destRow).at(move.destCol) = getPlayerToMove();
//Flip neighbours, then store move and flips.
for (int nbrRow = move.destRow-1; nbrRow <= move.destRow+1; ++nbrRow)
{
if (nbrRow < 0 || nbrRow >= getNRows())
continue;
for (int nbrCol = move.destCol-1; nbrCol <= move.destCol+1; ++nbrCol)
{
if (nbrCol < 0 || nbrCol >= getNCols())
continue;
if (board.at(nbrRow).at(nbrCol) == opposingPlayer)
{
//Flip the opposing neighbour.
board.at(nbrRow).at(nbrCol) = getPlayerToMove();
if (getPlayerToMove() == 1) {
++nRed; --nBlue;
} else {
++nBlue; --nRed;
}
moveAndFlips.setFlip(nbrRow - move.destRow, nbrCol - move.destCol);
}
}
}
}
movesAndFlips.push_back(moveAndFlips);
//Change the player to move.
playerToMove = opposingPlayer;
}
void undoLastMove()
{
assert(movesAndFlips.size() > 0);
//Unflip neighbours.
MoveAndFlippedNbrs lastMoveAndFlip = movesAndFlips.back();
int playerUndoingMove = (getPlayerToMove()==1)?2:1;
if (lastMoveAndFlip.move.isPass() == false)
{
for (int dRow = -1; dRow <= 1; ++dRow)
{
for (int dCol = -1; dCol <= 1; ++dCol)
{
if (lastMoveAndFlip.getFlip(dRow, dCol))
{
board.at(lastMoveAndFlip.move.destRow + dRow)
.at(lastMoveAndFlip.move.destCol + dCol) = getPlayerToMove();
if (getPlayerToMove() == 1) {
++nRed; --nBlue;
} else {
++nBlue; --nRed;
}
}
}
}
//Remove destination piece.
board.at(lastMoveAndFlip.move.destRow).at(lastMoveAndFlip.move.destCol) = 0;
//Restore source piece (redundanct if 'grow', but that okay.)
if (lastMoveAndFlip.move.isHop()) {
board.at(lastMoveAndFlip.move.srcRow).at(lastMoveAndFlip.move.srcCol) = playerUndoingMove;
} else {
if (playerUndoingMove == 1) {
--nRed;
} else {
--nBlue;
}
}
}
//Reduce history size by 1, and change player to move.
movesAndFlips.pop_back();
playerToMove = playerUndoingMove;
}
//Only a pass is legal if the player has nowhere to move. If two passes in a row occur,
//the game is over, and no further move is legal.
vector getLegalMoves()
{
vector legalMoves;
if (gameIsOver())
return legalMoves;
//Find 'grow' moves first. First, search for a blank tile.
for (int destRow = 0; destRow < getNRows(); ++destRow) {
for (int destCol = 0; destCol < getNCols(); ++destCol) {
if (getTileContents(destRow, destCol) != 0)
continue;
//Then, find a neighbouring source to grow from.
findNeighbouringSource(destRow, destCol, legalMoves);
}
}
//Now find 'hop' moves. Do this in a separate loop to perhaps increase alpha-beta efficiency.
for (int srcRow = 0; srcRow < getNRows(); ++srcRow)
{
for (int srcCol = 0; srcCol < getNCols(); ++srcCol)
{
if (getTileContents(srcRow, srcCol) != getPlayerToMove())
continue;
for (int destRow = srcRow - 2; destRow <= srcRow + 2; ++destRow)
{
if (destRow < 0 || destRow >= getNRows())
continue;
for (int destCol = srcCol - 2; destCol <= srcCol + 2; ++destCol)
{
if (destCol < 0 || destCol >= getNCols())
continue;
if (getTileContents(destRow, destCol) != 0)
continue;
//We've found a good 'hop' move?
Move candidateMove = Move::createMove(srcRow, srcCol, destRow, destCol);
if (candidateMove.isHop())
legalMoves.push_back(candidateMove);
}
}
}
}
//If no regular moves exist, a 'pass' is the only legal move.
if (legalMoves.size() == 0)
legalMoves.push_back(Move::createPass());
return legalMoves;
}
private:
void findNeighbouringSource(int destRow, int destCol, vector& legalMoves)
{
for (int srcRow = destRow - 1; srcRow <= destRow + 1; ++srcRow)
{
if (srcRow < 0 || srcRow >= getNRows())
continue;
for (int srcCol = destCol - 1; srcCol <= destCol + 1; ++srcCol)
{
if (srcCol < 0 || srcCol >= getNCols())
continue;
if (getTileContents(srcRow, srcCol) != getPlayerToMove())
continue;
legalMoves.push_back(Move::createMove(srcRow, srcCol, destRow, destCol));
return;
}
}
}
};
static void outputAtxGame(AtaxxGame& atxGame);
static MoveSequenceAndScore minimax(AtaxxGame& atxGame, int nPlies);
static MoveSequenceAndScore minimax_worker(AtaxxGame& atxGame, int nPlies, int nPliesMax,
int alpha, int beta);
int g_nMovesTried = 0;
int main()
{
AtaxxGame atxGame(7,2); //Set the number of rows and number of columns to any value >= 2.
atxGame.makeMove(Move::createMove(0,0,1,1)); //If you wish to investigate positions after the opening position, add lines which make moves here.
//atxGame.makeMove(Move::createMove(6,0,5,1)); // ...like so. Remove the first // on the left to enable this line, for example.
vector moves; // = atxGame.getLegalMoves(); <-- replace the semi-colon after 'moves' with the commented-out code, then delete all moves.push_back() commands to investigate _all_ legal moves from the given position.
moves.push_back(Move::createMove(6,0,5,0)); //I am investigating a subset of all possible moves here. Specifically, after 1.a1b1, I am only investigating 1...g1f1
moves.push_back(Move::createMove(6,0,5,1)); // and 1...g1f2.
for (int nPlies = 16; nPlies <= 16; ++nPlies) //Set the starting (>=1) and ending (>=starting) number of plies to search.
{
for (unsigned int iTrialMove = 0; iTrialMove < moves.size(); ++iTrialMove)
{
atxGame.makeMove(moves.at(iTrialMove));
outputAtxGame(atxGame);
g_nMovesTried = 0;
MoveSequenceAndScore mss = minimax(atxGame, nPlies);
cout << "L" << nPlies << " eval value, with " << g_nMovesTried << " moves tried, is "
<< mss.score << "." << endl << "Best line =";
for (unsigned int iBestLineMove = 0; iBestLineMove < mss.moves.size(); ++iBestLineMove) {
if (iBestLineMove % 2 == 0)
cout << ' ' << ((iBestLineMove/2)+1) << ".";
cout << ' ';
mss.moves.at(iBestLineMove).printToStdout();
atxGame.makeMove(mss.moves.at(iBestLineMove));
}
cout << endl << "leads to:" << endl;
outputAtxGame(atxGame);
cout << endl;
for (unsigned int iBestLineMove = 0; iBestLineMove < mss.moves.size(); ++iBestLineMove) {
atxGame.undoLastMove();
}
atxGame.undoLastMove();
}
}
return 0;
}
//Determine the 'best' move. Hides nPliesMax, alpha, beta details from user. This is a
//wrapper around minimax_worker, which should/will be 'private' somewhere soon.
static MoveSequenceAndScore minimax(AtaxxGame& atxGame, int nPlies)
{
return minimax_worker(atxGame, nPlies, nPlies, -100000, 100000);
}
static MoveSequenceAndScore minimax_worker(AtaxxGame& atxGame, int nPlies, int nPliesMax,
int alpha, int beta)
{
//these must have absolute values > or < to red win and blue win.
MoveSequenceAndScore bestMSS = MoveSequenceAndScore::scoreWithoutMove(0);
bestMSS.score = (atxGame.getPlayerToMove() == 1) ? -10000 : 10000;
vector moves = atxGame.getLegalMoves();
if (moves.size() == 0) {
//the game is over.
if (atxGame.getNRed() > atxGame.getNBlue())
return MoveSequenceAndScore::scoreWithoutMove(1000 + (atxGame.getNRed() - atxGame.getNBlue()));
else if (atxGame.getNRed() < atxGame.getNBlue())
return MoveSequenceAndScore::scoreWithoutMove(-1000 - (atxGame.getNBlue() - atxGame.getNRed()));
else
return MoveSequenceAndScore::scoreWithoutMove(0);
}
for (unsigned int iMove = 0; iMove < moves.size() && alpha <= beta; ++iMove)
{
atxGame.makeMove(moves.at(iMove));
++g_nMovesTried;
MoveSequenceAndScore evalValueAndMoveSeq = MoveSequenceAndScore::scoreWithoutMove(0);
if (nPlies == 1) {
if (atxGame.gameIsOver()) {
if (atxGame.getNRed() > atxGame.getNBlue())
evalValueAndMoveSeq.score = 1000 + (atxGame.getNRed() - atxGame.getNBlue());
else if (atxGame.getNRed() < atxGame.getNBlue())
evalValueAndMoveSeq.score = -1000 - (atxGame.getNBlue() - atxGame.getNRed());
else
evalValueAndMoveSeq.score = 0;
} else {
evalValueAndMoveSeq.score = atxGame.getNRed() - atxGame.getNBlue();
if (moves.at(iMove).isPass()) { //check for one player being trap-defeated.
if (atxGame.getPlayerToMove() == 1) { //red has the option to fill
int finalDiff = atxGame.getNRed() + atxGame.getNBlank() - atxGame.getNBlue();
if (finalDiff > 0) { //red will win, _if_ red can see that far.
evalValueAndMoveSeq.score = 1000 + finalDiff;
}
} else {
int finalDiff = atxGame.getNBlue() + atxGame.getNBlank() - atxGame.getNRed();
if (finalDiff > 0) { //blue will win, _if_ blue can see that far.
evalValueAndMoveSeq.score = -1000 - finalDiff;
}
}
}
}
}
else {
evalValueAndMoveSeq = minimax_worker(atxGame, nPlies - 1, nPliesMax, alpha, beta);
}
//tack this move onto the sequence.
evalValueAndMoveSeq.moves.insert(evalValueAndMoveSeq.moves.begin(), moves.at(iMove));
if (atxGame.getPlayerToMove() == 2 && evalValueAndMoveSeq.score > bestMSS.score)
{
//red, the maximizer, just moved.
bestMSS = evalValueAndMoveSeq;
if (bestMSS.score > alpha)
alpha = evalValueAndMoveSeq.score;
}
else if (atxGame.getPlayerToMove() == 1 && evalValueAndMoveSeq.score < bestMSS.score)
{
//blue, the minimizer, just moved.
bestMSS = evalValueAndMoveSeq;
if (bestMSS.score < beta)
beta = evalValueAndMoveSeq.score;
}
atxGame.undoLastMove();
}
return bestMSS;
}
//Output the board to stdout.
void outputAtxGame(AtaxxGame& atxGame)
{
cout << "Moves so far:";
for (int iMove = 0; iMove < atxGame.nMovesMade(); ++iMove) {
if (iMove % 2 == 0)
cout << ' ' << ((iMove/2)+1) << ".";
cout << ' ';
atxGame.getMoveMade(iMove).printToStdout();
}
cout << endl;
for (int iRow = 0; iRow < atxGame.getNRows(); ++iRow) {
for (int iCol = 0; iCol < atxGame.getNCols(); ++iCol) {
switch (atxGame.getTileContents(iRow,iCol)) {
case 0:
cout << '-'; break;
case 1:
cout << 'r'; break;
case 2:
cout << 'b'; break;
default:
assert(false);
}
}
if (iRow < atxGame.getNRows() - 1)
cout << endl;
}
cout << " , " << ((atxGame.getPlayerToMove()==1)?'r':'b') << " to move, score is "
<< atxGame.getNRed() << " to " << atxGame.getNBlue() << "." << endl;
}
               (
geocities.com/mark_gamez)