This is ComputerPlayer.m in view mode; [Download] [Up]
/*
* ComputerPlayer
* description: a generic class for computer game players. It implements a
* threaded, sorted, alpha beta search tree.
* history:
* 2/15/93 [Erik Kay] - created
* todo:
* make it think ahead all of the time
*/
#import "ComputerPlayer.h"
// initial cthread call
void waitForTurn (id self)
{
[self waitForTurn];
}
@implementation ComputerPlayer
// initilialization
- initWithRules:(Rules *)r andPieceType:(square_state)type;
{
[super initWithRules:r andPieceType:type];
beingFreed = NO;
sorting = YES; // sort by default
deterministic = NO; // add in a random factor at the top level
srandom(time(0));
searchDepth = 1;
myTurn = condition_alloc();
myLock = mutex_alloc();
mutex_lock(myLock);
// spawn off the thinking thread
cthread_detach(cthread_fork((cthread_fn_t)waitForTurn,self));
return self;
}
// set the game (our delegate)
- setGame:g
{
[super setGame:g];
server = [NXConnection connectToPort:[g inPort]];
return self;
}
- free
{
beingFreed = YES;
if (playerName)
free(playerName);
// let the othe thread know that it's time to clean up
condition_signal(myTurn);
// give the thread a chance to clean up
//! this should be done using a mutex rather than some arbitrary delay
usleep(100);
[super free];
return self;
}
// the base strategy implemented here is greedy
//! this should really be an abstract class with no strategy implemented
+ (const char *)strategyName
{
return "Greedy";
}
- (char *)playerName
{
if (!playerName)
return (char *)[[self class] strategyName];
else return playerName;
}
// here's where the player waits when it's not its turn
- waitForTurn
{
mutex_unlock(myLock);
while (1) {
// wait for our turn
condition_wait(myTurn, myLock);
mutex_unlock(myLock);
// we're being freed. Clean up and exit rather than do a move
if (beingFreed) {
mutex_unlock(myLock);
cthread_exit(0);
return self;
} else
[self reallyDoNextMove]; // do it
}
return self;
}
// sort a list of boards by score using merge sort
- (int)partition:(List *)boards from:(int)first to:(int)last
{
int left, right, x;
Board *a, *l;
left = first;
right = last;
l = [boards objectAt:last];
x = l->score;
while (left < right) {
a = [boards objectAt:left];
while ((left < right) && (a->score <= x) ) {
left++;
a = [boards objectAt:left];
}
if (left < right) {
[boards replaceObjectAt:right with:a];
right --;
}
a = [boards objectAt:right];
while ((left < right) && (a->score <= x)) {
right--;
a = [boards objectAt:right];
}
if (left < right) {
[boards replaceObjectAt:left with:a];
left++;
}
}
if (right != last)
[boards replaceObjectAt:right with:l];
return right;
}
- merge:(List *)boards first:(int)first middle:(int)middle last:(int)last
{
int x,y;
Board *a, *b;
x = first;
y = middle;
while ((x < middle) && (y < last)) {
a = [boards objectAt:x];
b = [boards objectAt:y];
if (a->score > b->score) {
[boards replaceObjectAt:x with:b];
[boards replaceObjectAt:y with:a];
x++;
continue;
} else y++;
}
return self;
}
- sortMoves:(List *)boards from:(int)first to:(int)last
{
int middle;
if (first < last) {
middle = (first + last) / 2;
[self sortMoves:boards from:first to:middle];
[self sortMoves:boards from:(middle + 1) to:last];
[self merge:boards first:first middle:middle last:last];
}
return self;
}
- sortMoves:(List *)boards
{
int c, i, score;
Board *b;
c = [boards count];
for (i = 0; i < c; i++) {
b = [boards objectAt:i];
score = [self scoreBoard:b forPlayer:pieceType];
b->score = score;
}
[self sortMoves:boards from:0 to:(c-1)];
return self;
}
// what is called to let us know that it's our turn
- doNextMove:(Board *)b
{
currentBoard = b;
mutex_lock(myLock);
condition_signal(myTurn); // tell the other thread to go for it
mutex_unlock(myLock);
return self;
}
// here's where the other thread really does the next move
- reallyDoNextMove
{
move mv;
mv = [self nextMove];
// if we're still active, tell the main game what move to do
if (currentState == PLAYER_ACTIVE)
[server startMove:&mv];
return self;
}
// README: if you don't want to use the alpha/beta search demonstrated here,
// just override nextMove and implement your own method
- (move)nextMove
{
int i, count, score, alpha = MININT;
Board *tmpb, *maxBoard = nil;
List *validMoves; // a list of boards
move mv;
struct timeval t;
struct timezone tz;
long orig = 0;
if (debug) {
gettimeofday(&t,&tz);
orig = t.tv_sec;
totalNodes = 0;
numPruned = 0;
}
// get all of the valid moves for this player on the current board
tmpb = currentBoard;
validMoves = [rules validMoves:tmpb forPlayer:pieceType];
// sort those boards
if (sorting)
[self sortMoves:validMoves];
// do the top level AB search
count = [validMoves count];
if (debug)
totalNodes += count;
for (i = 0; i < count; i++) {
tmpb = [validMoves objectAt:i];
score = [self ABSearch:tmpb atDepth:(searchDepth - 1)
forPlayer:OTHER_PLAYER(pieceType)
alpha:alpha
beta:MAXINT];
// prune away
if (score > alpha) {
alpha = score;
maxBoard = tmpb;
}
// dprintf(("score: %d alpha:%d\n",score,alpha));
}
if (!maxBoard)
mv.from.row = mv.from.col = mv.to.col = mv.to.row = -1;
else
mv = *[maxBoard currentMove];
[[validMoves freeObjects] free];
mutex_lock(myLock);
// keep debugging stats
if (debug) {
gettimeofday(&t,&tz);
moveTime = t.tv_sec - orig;
pruningPercent = (numPruned * 100) / totalNodes;
}
dprintf (("winning score: %d (%d,%d) to (%d,%d)\n",alpha,
mv.from.col, mv.from.row, mv.to.col, mv.to.row));
return mv;
}
// the main alpha/beta search
- (int)ABSearch:(Board *)b atDepth:(int)d
forPlayer:(square_state)player
alpha:(int)alpha
beta:(int)beta
{
int i, count, score;
Board *tmpb;
List *validMoves; // a list of boards
totalNodes++;
// if we're at the bottom of the tree, just score the board and return
if (d == 0) {
numLeaves++;
score = [self scoreBoard:b forPlayer:pieceType];
if (!deterministic)
score += (random() & 0x1); //! slow!
return score;
}
// get the valid moves for this board and sort them
validMoves = [rules validMoves:b forPlayer:player];
if (sorting)
[self sortMoves:validMoves];
count = [validMoves count];
if (debug)
totalNodes += count;
// cycle through the valid moves
// minimize or maximize depending on which level we're on
i = 0;
if (player != pieceType) { /* minimizing level */
while ((i < count) && (alpha < beta)) {
tmpb = [validMoves objectAt:i];
score = [self ABSearch:tmpb atDepth:(d - 1)
forPlayer:OTHER_PLAYER(player)
alpha:alpha
beta:beta];
if (score < beta)
beta = score;
i++;
}
if (debug)
if (alpha >= beta) {
dprintf(("Pruned %f%% of branches at level %d\n",
100.0 * (count - i)/(count*1.0), d));
numPruned += count - i;
}
[[validMoves freeObjects] free];
return beta;
} else { /* maximizing level */
while ((i < count) && (alpha < beta)) {
tmpb = [validMoves objectAt:i];
score = [self ABSearch:tmpb atDepth:(d - 1)
forPlayer:OTHER_PLAYER(player)
alpha:alpha
beta:beta];
if (score > alpha)
alpha = score;
i++;
}
if (debug)
if (alpha >= beta) {
dprintf(("Pruned %f%% of branches at level %d\n",
100.0 * (count - i)/(count*1.0), d));
numPruned += count - i;
}
[[validMoves freeObjects] free];
return alpha;
}
}
// READ THIS - IMPORTANT
// This is the most important method if you're writing your own computer
// player. The easiest way to do this, is to subclass ComputerPlayer and to
// override scoreBoard:forPlayer:. It just provides an absolute number that
// will rate a move.
// The example provided here is a simple greedy implementation.
-(int)scoreBoard:(Board *)b forPlayer:(square_state)type
{
return ([b numberOfPiece:type] - [b numberOfPiece:OTHER_PLAYER(type)]);
}
// set how deep the tree should be
- setSearchDepth:(int)depth
{
int numlen, len;
searchDepth = depth;
numlen = (depth / 10) + 1;
if (playerName) {
free(playerName);
playerName = NULL;
}
len = strlen([[self class] strategyName]) + numlen + 2;
playerName = malloc(len);
sprintf(playerName,"%s %d",[[self class] strategyName], depth);
return self;
}
- (int)searchDepth
{
return searchDepth;
}
// debugging info
- (int)moveTime
{
return moveTime;
}
- (int)numLeaves
{
return numLeaves;
}
- (int)pruningPercent
{
return pruningPercent;
}
@end
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.