root/ggpa/QLearner.cpp

/*
 * QLearner.cpp
 * Class that will handle the QLearning algorithm
 */



#include "QLearner.h"

#include <string>
#include <iostream>
#include "GameWorld.h"
#include "QFunction.h"
#include "QNeuralNetwork.h"
#include "State.h"
#include "Action.h"

#define GAMMA 0.3


/*
 * Initializes the QLearner to learn on the given world.
 */
QLearner::QLearner(GameWorld* world) {
    gameWorld = world;
    qFunction = new QNeuralNetwork(gameWorld->getState()->getSize(), 5);
}

/*
 * learn
 * Parameters: learnTime - the amount of time allowed for learning.
 *                         by default it will use the time dictated
 *                         in the GameWorld class.
 * Return type: none.
 * Begins training on the given game.
 */
void QLearner::learn(double learnTime) {
    if (learnTime == DEFAULT_LEARN_TIME) {
        learnTime = gameWorld->getStartClock();
    }

    gameWorld->startGame();

    // NOTE: timing measure is temporary!!!!!
    for (int count = 0; count < learnTime; count++) {
        // perform a learning iteration.
        if (gameWorld->isDone()) {
            gameWorld->startGame();
        }

        State* state = gameWorld->getState();

        vector<Action*> legalMoves = gameWorld->getLegalMoves();
        Action* action = chooseMove(legalMoves);

        // perform the action in the GameWorld
        performAction(action);

        State* newState = gameWorld->getState();
        vector<Action*> newActions = gameWorld->getLegalMoves();
        
        int reward = gameWorld->getReward(gameWorld->getRole());
        double nextUtility = getMaxUtility(newState, newActions);

        // update the utility
        updateUtility(state, action, reward, nextUtility);
    }
    
}

/*
 * getAction
 * Parameters: decisionTime - the amount of time allowed for making the
 *                            decision.  By default, the time stored
 *                            in the GameWorld class is used.
 * Return type: Action*
 * Returns an action for the current state
 */
Action* QLearner::getAction(double decisionTime) {
    // get the current state
    State* state = gameWorld->getState();

    // get the possible actions
    vector<Action*> actions = gameWorld->getLegalMoves();

    // find the action with the highest utility
    double maxUtility = 0;
    Action* bestAction = NULL;
    for (unsigned int i = 0; i < actions.size(); i++) {
        double utility = qFunction->getValue(*state, *(actions[i]));
        if (bestAction == NULL || utility > maxUtility) {
            maxUtility = utility;
            bestAction = actions[i];
        }
    }

    return bestAction;
}

/**
 * performAction
 * Parameters: action - the action to perform
 * Return type: none
 * Performs the action in the game world, handling any extra overhead
 */
void QLearner::performAction(Action* action) {
    vector<string> roles = gameWorld->getRoles();
    vector<Action*> actions(roles.size());
    
    for (unsigned int roleNum = 0; roleNum < roles.size(); roleNum++) {
        if (roles[roleNum] == gameWorld->getRole()) {
            actions[roleNum] = action;
        } else {
            vector<Action*> possibleActions
                = gameWorld->getLegalMoves(roles[roleNum]);
            actions[roleNum] = getRandomMove(possibleActions);
        }
    }

    // call the update
    gameWorld->update(actions);
}

/**
 * getMaxUtility
 * Parameters: state - the current state
 *             actions - the set of actions we are interested in
 * Return type: double
 * Returns the maximum value for the QFunction over all of the actions.
 */
double QLearner::getMaxUtility(State* state, vector<Action*> actions) {
    double max = 0;
    for (unsigned int actionIndex = 0; actionIndex < actions.size(); 
         actionIndex++) {
        Action* action = actions[actionIndex];
        double utility = qFunction->getValue(*state, *action);
        if (utility > max) {
            max = utility;
        }
    }
    return max;
}

/*
 * updateUtility
 * Parameters: state - the current state
 *             action - the current action
 *             reward - the immediate reward
 *             nextUtility - the expected utility of the resulting state
 * No return type
 * Updates the utility for the given state-action pair to a value
 * determined by reward and nextUtility.
 */
void QLearner::updateUtility(State* state, Action* action, int reward, 
                   double nextUtility) {
    double utility = reward + GAMMA * nextUtility;
    qFunction->update(*state, *action, utility);
}



/*
 * chooseMove
 * Parameters: possibleActions - a vector of actions to choose from
 * Return type: Action*
 * Returns one of the actions from the vector.  This function is intended
 * for use with the primary role during the learning process.  Using it
 * in other conditions may give unexpected results.
 */
Action* QLearner::chooseMove(vector<Action*> possibleActions) const {
    // initialize the weights vector
    vector<double> weights(possibleActions.size());
    for (unsigned int i = 0; i < possibleActions.size(); i++) {
        weights[i] = qFunction->getValue(*gameWorld->getState(), 
                                        *possibleActions[i]);
    }

    // randomly choose an action according to these weights
    return getRandomMove(possibleActions, weights);
}

/*
 * getRandomMove
 * Parameters: possibleActions - a vector of actions to choose from
 * Return type: Action*
 * Randomly selects one of the actions from the vector.  Random seeding
 * is not handled in this function.
 */
Action* QLearner::getRandomMove(vector<Action*> possibleActions) const {
    // initialize a weights vector
    vector<double> weights(possibleActions.size());
    for (unsigned int num = 0; num < possibleActions.size(); num++) {
        weights[num] = 1.0;
    }
    
    // call the other getRandomMove function
    return getRandomMove(possibleActions, weights);
}

/*
 * getRandomMove
 * Parameters: possibleActions - a vector of actions to choose from
 *             weights - a vector of double representing the weights
 *                       for each of the actions.
 * Return type: Action*
 * Randomly selects one of the actions from the vector based on the 
 * distribution defined by weights.  This does not need to be normalized.
 */
Action* QLearner::getRandomMove(vector<Action*> possibleActions, 
                                vector<double> weights) const {
    // determine the number of actions to be considered
    unsigned int maxIndex = possibleActions.size();
    if (weights.size() < possibleActions.size()) {
        maxIndex = weights.size();
    }

    if (maxIndex == 0) {
        cerr << "Empty set of actions" << endl;
        exit(1);
    }

    // sum up the weights
    double sum = 0;
    for (unsigned int i = 0; i < maxIndex; i++) {
        sum += weights[i];
    }

    // get the random number
    double randomNumber = sum * (rand() / (RAND_MAX + 1.0));
    
    // find the corresponding action
    double curMax = 0;
    for (unsigned int i = 0; i < maxIndex; i++) {
        curMax += weights[i];
        if (randomNumber <= curMax) {
            return possibleActions[i];
        }
    } 

    // should never get here
    cerr << "No action was selected! curMax = " << curMax << " rand = " 
         << randomNumber << endl;
    exit(1);
    
}