OptimalNimPlayer.cpp (cpp-lecture/nim2player/OptimalNimPlayer.cpp)

      1
      2
      3
      4
      5
      6
      7
      8
      9
     10
     11
     12
     13
     14
     15
     16
     17
     18
     19
     20
     21
     22
     23
     24
     25
     26
     27
     28
     29
     30
     31
     32
     33
     34
     35
     36
     37
     38
     39
     40
     41
     42
     43
     44
     45
     46
     47
     48
     49
     50
     51
     52
     53
     54
     55
     56
     57
     58
     59
     60
     61
     62
     63
     64
     65
     66
     67
     68
     69
     70

#include "OptimalNimPlayer.hpp"
#include <iostream>
#include <random>

OptimalNimPlayer::OptimalNimPlayer()
    : name("OptimalNimPlayer")
{
}

const std::string&
OptimalNimPlayer::get_name() const
{
    return name;
}

NimMove
OptimalNimPlayer::get_move(const NimGame& game) const
{
    std::mt19937    randomDev;
    unsigned int    number_of_heaps = game.get_number_of_heaps();
    unsigned int    numMoves = 0;
    NimMove         move;

    if (game.nim_value() != 0) {
        // find all winning moves
        unsigned int maxtake = game.get_max_take();
        for (unsigned int i = 0; i < number_of_heaps; ++i) {
            unsigned int max = game.get_heap_size(i);
            if (maxtake && max > maxtake) {
                max = maxtake;
            }
            for (unsigned int count = 1; count <= max; ++count) {
                NimGame test = game;
                test.execute_move(move);
                if (test.nim_value() == 0) {
                    ++numMoves;
                    std::uniform_int_distribution<unsigned int> dis(0,numMoves-1);
                    if (numMoves==1 || dis(randomDev)==0) {
                        move = NimMove(i, 1);
                    }
                }
            }
        }
    }
    if (move.has_resigned()) {
        // bad luck
        for (unsigned int i=0; i<number_of_heaps; ++i) {
            if (game.get_heap_size(i)>0) {
                ++numMoves;
                std::uniform_int_distribution<unsigned int> dis(0,numMoves-1);

                if (numMoves==1 || dis(randomDev)==0) {
                    move = NimMove(i, 1);
                }
            }
        }
    }
    // select one of the selected moves by random
    return move;
}

// support dynamic loading
extern "C" {

NimPlayer*
construct() {
    return new OptimalNimPlayer();
}

} // extern "C"