Browse Files
       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
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      82
      83
      84
      85
      86
      87
      88
      89
      90
      91
      92
      93
      94
      95
      96
      97
      98
      99
     100
     101
     102
     103
     104
     105
     106
     107
     108
     109
     110
     111
     112
     113
     114
     115
     116
     117
     118
     119
     120
     121
     122
     123
     124
     125
     126
     127
     128
     129
     130
     131
     132
     133
     134
     135
     136
     137
     138
     139
     140
#ifndef NIM_GAME_HPP
#define NIM_GAME_HPP

#include <cassert>
#include <vector>
#include "NimMove.hpp"
#include "Table.hpp"
#include "Nim.hpp"
#include "NimParameters.hpp"


template<unsigned int max_heap_size, unsigned int ... possible_moves>
class NimGame {
   public:
      template <unsigned int N>
      struct ComputeNimValue {
     static constexpr unsigned int value = Nim<N, possible_moves...>::value;
      };
      template <unsigned int N>
      struct ValidMove {
     static constexpr unsigned int value =
        IsMemberInSet<N, possible_moves...>::is_member;
      };
      using NimValues = Table<max_heap_size+1, ComputeNimValue>;
      using ValidMoves = Table<max_heap_size+1, ValidMove>;

      static constexpr unsigned int moves_len = sizeof...(possible_moves);
      typedef unsigned int moves_type[moves_len];
      static constexpr unsigned int moves[] = {possible_moves...};

      /* initialize a game of Nim with the given number of
     heaps where a move must be out of moves */
      NimGame(unsigned int _number_of_heaps) :
     number_of_heaps(_number_of_heaps),
     heap_size(_number_of_heaps),
     resigned(false),
     next_player(PLAYER1) {
      }

      /* return the number of heaps */
      unsigned int get_number_of_heaps() const {
     return number_of_heaps;
      }

      /* initialize the given heap (index starting from 0) to
     the given size which much be <= max_heap_size */
      void set_heap_size(unsigned int index, unsigned int size) {
     assert(index < number_of_heaps && size <= max_heap_size);
     heap_size[index] = size;
      }

      /* retrieve the size of the given heap (index starting from 0) */
      unsigned int get_heap_size(unsigned int index) const {
     assert(index < number_of_heaps);
     return heap_size[index];
      }

      /* PLAYER1 is the player who plays/played the first move */
      typedef enum {PLAYER1, PLAYER2} Player;

      /* is the game finished? */
      bool finished() const {
     if (resigned) return true;
     for (unsigned int size: heap_size) {
        if (size >= moves[0]) return false;
     }
     return true;
      }

      /* if yes, who has won?
     PRE: finished() returns true */
      Player winner() const {
     assert(finished());
     if (next_player == PLAYER1) {
        return PLAYER2;
     } else {
        return PLAYER1;
     }
      }

      /* otherwise, whose turn is next?
         PRE: finished() returns false */
      Player get_next_player() const {
     assert(!finished());
     return next_player;
      }

      /* is the given move valid?
     PRE: finished() returns false */
      bool valid_move(NimMove move) const {
     assert(!finished());
     // always accept a resignation
     if (move.has_resigned()) return true;
     // regular move
     return move.get_heap() < number_of_heaps &&
        move.get_count() <= heap_size[move.get_heap()] &&
        ValidMoves::val[move.get_count()];
      }

      /* execute the given move
     PRE: finished() returns false and valid_move(move) true */
      void execute_move(NimMove move) {
     assert(valid_move(move));
     if (move.has_resigned()) {
        // accept resignation
        resigned = true;
     } else {
        // regular move
        heap_size[move.get_heap()] -= move.get_count();
        switch (next_player) {
           case PLAYER1: next_player = PLAYER2; break;
           case PLAYER2: next_player = PLAYER1; break;
        }
     }
      }

      /* compute the nim value for the current state of the game */
      unsigned int nim_value() const {
     unsigned int val = 0;
     for (unsigned int size: heap_size) {
        val ^= NimValues::val[size];
     }
     return val;
      }

   private:
      const unsigned int number_of_heaps;
      std::vector<unsigned int> heap_size; // size of each of the heaps
      bool resigned; // the current player has resigned
      Player next_player;
};

#ifdef NIM_GAME_DEFINE
/* define the associated static member, if requested */
template<unsigned int max_heap_size, unsigned int ... possible_moves>
constexpr typename NimGame<max_heap_size, possible_moves...>::moves_type
   NimGame<max_heap_size, possible_moves...>::moves;
#endif

#endif