Othello - Code Sample

#include <time.h>
#include <limits.h>
#include <cstdio>
#include "othello.h"
#include "minimax.h"
#include <windows.h>

#include "workqueue.h"
#include "ConditionVarible.h"

/*
The maximum time to spend calculating one move.
The actual time spent may be up to 0.1 seconds
longer than the value set here.
*/
const float max_time = 9.9f;

//Our work queue
WorkQueue mWork;

//Used to wake the threads when they pause
ConditionVarible restart;

//Info on the threads
HANDLE* threads = 0;
DWORD ThreadCount = 0;

//This is the worker thread. The param is a thread-unique ID.
unsigned int _stdcall
do_minimax_parallel(void* param)
{
    //This conversion likes to cause warnings that don't matter
    #pragma warning(push)
    #pragma warning(disable: 4311)
    unsigned int threadID = reinterpret_cast<unsigned int>(param);
    #pragma warning(pop)

    mWork.AddThread(threadID);

    do
    {
        //Grab the next work item.
        Work work;
        int level;
        EnterCriticalSection(mWork.getQueueAccessLock());
        do
        {
            level = mWork.Pop(&work);
            //If this is a sicken pill, hold. We will be using this thread again, however
            if (work.valid == Work::VAL_Sicken)
                restart.Wait(mWork.getQueueAccessLock());
            //If this is a kill pill, exit. The thread is no longer needed.
            else if (work.valid == Work::VAL_Kill)
            {
                LeaveCriticalSection(mWork.getQueueAccessLock());
                return 0;
            }
        } while (work.valid != Work::VAL_Food);
        LeaveCriticalSection(mWork.getQueueAccessLock());

        //If the board is full, this work item is complete
        if (work.original_board.full())
            continue;

        //Get a list of all moves the player can legally make
        othello::move_iterator iter = work.original_board.get_available_moves(work.player);

        /*
        Save the value of the move.
        If this is not the first pass, save the orignal move, otherwise, save this move.
        */
        if (work.base_move.col != 255)
            mWork.UpdateMove(level, evaluate_board(work.original_board, iter, work.basePlayer), (work.player == work.basePlayer), work.base_move);
        else
            mWork.UpdateMove(level, evaluate_board(work.original_board, iter, work.basePlayer), (work.player == work.basePlayer), iter.get());

        //Add any additional moves we can make now onto the queue for evalulation
        if (!iter.valid()) {
            if (work.last_was_empty)
                continue;
            else
                mWork.Push(Work(work.original_board, work.base_move, 1 - work.player, work.basePlayer, true), level + 1);
        }

        while (iter.valid()) {
            const othello::move this_move = iter.get();

            /* Using the next available move, create updated board
             * state to test.
             */
            othello::board updated_board(work.original_board);
            updated_board.place_piece(this_move, work.player);

            if (work.base_move.col < 255)
                mWork.Push(Work(updated_board, work.base_move, 1 - work.player, work.basePlayer, false), level + 1);
            else
                mWork.Push(Work(updated_board, this_move, 1 - work.player, work.basePlayer, false), level + 1);

            iter.next();

            //Exit if all work has been completed
            if (mWork.checkPoison())
                break;
        }
    } while (true);

    //We should never get here...this is just to prevent compile warnings.
    return 1;
}

//We are done. Kill all threads.
void exitMinimax()
{
    mWork.Poison(Work::VAL_Kill);
    DWORD err = WaitForMultipleObjects(ThreadCount, threads, TRUE, INFINITE);
    if (err != 0)
    {
        DWORD num = GetLastError();
        printf("WaitForMultipleObjects() returned with error #%i.\n", num);
    }
    delete [] threads;
}

/**
 * Use minimax search to select the player's move
 *
 * \param b      Original board configuration
 * \param player Player whose move is to be selected
 * \param m      Location to store the player's move
 */
void get_move_parallel(const othello::board &b, unsigned player,
          struct othello::move &m)
{
    //Some timing values, used to check performance
    clock_t before[2];
    clock_t after;
    clock_t elapsed;
    float seconds;

    before[0] = clock();

    //Clear out old data
    printf("\n\nClearing Old Data.\n");
    mWork.Clear();

    before[1] = clock();

    //Push initial work
    othello::move tMove;
    tMove.col = ~0;
    tMove.row = ~0;
    mWork.Push(Work(b, tMove, player, player, false), 0);

    //Begin the work
    if (threads == 0)
    {
        //Calculate number of threads
        {
            SYSTEM_INFO info;
            GetSystemInfo(&info);
            //*
            ThreadCount = info.dwNumberOfProcessors;
            /*/
            ThreadCount = 1;
            //*/
            printf("Using %i worker threads.\n", ThreadCount);
        }
        mWork.setThreadCount(ThreadCount);

        //Begin the threads
        threads = new HANDLE[ThreadCount];
        #pragma warning(push)
        #pragma warning(disable: 4312)
        for (unsigned int x = 0; x < ThreadCount; x++)
            threads[x] = HANDLE(_beginthreadex(0, 0, do_minimax_parallel, reinterpret_cast<void*>(x), 0, 0));
        #pragma warning(pop)
    }
    else
    {
        printf("Beginning.\n");
        //Restart the workers
        restart.Broadcast();
    }

    //Sleep until all work is complete or the timer has expired
    do
    {
        Sleep(100);
        after = clock();
        elapsed = after - before[0];
        seconds = float(elapsed) / float(CLOCKS_PER_SEC);
    } while ((seconds <= max_time) && (!mWork.isPoisoned()));

    //Halt all workers
    printf("Poisoning.\n");
    mWork.Poison();
    printf("Poisoned.\n");

    //Performance analysis stuff
    printf("Got to level: %u\n", mWork.getBaseLevel());
    m = mWork.GetBestMove();

    after = clock();
    elapsed = after - before[0];
    seconds = float(elapsed) / float(CLOCKS_PER_SEC);
    printf("%.2f seconds from before clear\n", seconds);

    elapsed = after - before[1];
    seconds = float(elapsed) / float(CLOCKS_PER_SEC);
    printf("%.2f seconds from after clear\n\n", seconds);
}