ftp.nice.ch/pub/next/games/network/Splat.1.0.s.tar.gz#/Splat-1.0/ComputerPlayer.m

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 Marcel Waldvogel and Netfuture.ch.