Source

python-ai / src / othello / MinimaxPlayer.cpp

Full commit
#include "MinimaxPlayer.hpp"
#include <limits>
#include <cstdlib>
#include <iostream>

using std::cout;
using std::endl;

const double INF = std::numeric_limits<double>::max();
const double realRand()
    { return ((double)rand()/(double)RAND_MAX); }

MinimaxPlayer::MinimaxPlayer(const BoardPlayerNum num) : Player(num) {
    maxDepth = 3;
    endTime = time(NULL);
    
    // Random parameter tweaking
    srand((unsigned)(time(NULL) + num*31));
    weightStartScore =    -0.04 * (0.5 + realRand());
    weightStartCorners =   2.44 * (0.5 + realRand());
    weightStartMoves =     3.89 * (0.5 + realRand());
    weightEndScore =       1.05 * (0.5 + realRand());
    weightEndCorners =     0.42 * (0.5 + realRand());
    weightEndMoves =       0.48 * (0.5 + realRand());
    cout << "Board " << (int)num << " parameters: " << endl;
    cout << "    weightStartScore:    " << (double)weightStartScore << endl;
    cout << "    weightStartCorners:  " << (double)weightStartCorners << endl;
    cout << "    weightStartMoves:    " << (double)weightStartMoves << endl;
    cout << "    weightEndScore:      " << (double)weightEndScore << endl;
    cout << "    weightEndCorners:    " << (double)weightEndCorners << endl;
    cout << "    weightEndMoves:      " << (double)weightEndMoves << endl;
}

const BoardLoc MinimaxPlayer::chooseMove(const Board state, const BoardLocs locs) {
    // cout << "REM: " << state.featureUnpicked() << endl;
    endTime = time(NULL) + 18;
    BoardLoc bestMove = *(locs.begin());
    Value bestValue = -INF;
    BoardLocs::const_iterator it;
    cout << "EVALUATION: " << evaluate(state, playerNum) << endl;
    for(it = locs.begin(); it != locs.end(); it++) {
        const Board nextState = state.extend(*it, playerNum);
        const Value value = minValue(nextState, maxDepth, -INF, INF);
        if(value > bestValue) {
            bestMove = *it;
            bestValue = value;
        }
        // cout << Board::boardLocToString(*it) << ": " << value << endl;
    }
    return bestMove;
}

Value MinimaxPlayer::maxValue(const Board state, const int16_t depth,
                              const double alpha, const double beta) const {
    BoardPlayerNum player = playerNum;
    if(noAvailableMoves(state, player) || (depth == 0) || outOfTime()) {
        return evaluate(state, player);
    }
    Value bestAlpha = alpha;
    BoardLocs locs = state.validMoves(player);
    BoardLocs::const_iterator it;
    for(it = locs.begin(); it != locs.end(); it++) {
        const Board nextState = state.extend(*it, player);
        const Value value = minValue(nextState, depth-1, bestAlpha, beta);
        if(value > bestAlpha) bestAlpha = value;
        if(beta < bestAlpha) break;
    }
    return bestAlpha;
}

Value MinimaxPlayer::minValue(const Board state, const int16_t depth,
                              const double alpha, const double beta) const {
    BoardPlayerNum player = otherNum;
    if(noAvailableMoves(state, player) || (depth == 0) || outOfTime()) {
        return evaluate(state, player);
    }
    Value bestBeta = beta;
    BoardLocs locs = state.validMoves(player);
    BoardLocs::const_iterator it;
    for(it = locs.begin(); it != locs.end(); it++) {
        const Board nextState = state.extend(*it, player);
        const Value value = maxValue(nextState, depth-1, alpha, bestBeta);
        if(value < bestBeta) bestBeta = value;
        if(bestBeta < alpha) break;
    }
    return bestBeta;
}

inline Value MinimaxPlayer::evaluate(const Board state, const BoardPlayerNum player) const {
    const BoardPlayerNum other = Board::otherPlayer(player);
    return evaluatePlayer(state, player) - evaluatePlayer(state, other);
}

inline Value MinimaxPlayer::evaluatePlayer(const Board state, const BoardPlayerNum player) const {
    if(state.complete()) {
        return 1000.0 * state.featureScore(player);
    }
    const Feature rem = state.featureUnpicked();
    const Feature featureScore = state.featureScore(player);
    const Feature featureCorners = state.featureCorners(player);
    const Feature featureMoves = state.featureMoves(player);
    Value value = 0.0;
    value += rem * weightStartScore * featureScore;
    value += rem * weightStartCorners * featureCorners;
    value += rem * weightStartMoves * featureMoves;
    value += (1.0 - rem) * weightEndScore * featureScore;
    value += (1.0 - rem) * weightEndCorners * featureCorners;
    value += (1.0 - rem) * weightEndMoves * featureMoves;
    return value;
}

inline bool MinimaxPlayer::outOfTime() const {
    return (time(NULL) >= endTime);
}