Memorization with the minimax algorithmH

[AlexFZ]

Hey guys,

BEGIN UNNECESSARY INFORMATION:
I'm a past CS4 student over at RIT, and this is a questioning about an old project we were assigned. I completed the project already, but we used my partner's backend. I'm trying to re-do the project so I get the full practice myself, and to make sure that I understand all the concepts.

The project is basically to make a generic game engine that makes decisions for 2 player games using the minimax algorithm. Then we had to make 4 games that use the engine for decision making (takeaway, kayles, connect-3, and crossout).
END UNNECESSARY INFORMATION

I have the minimax decision making down fine (at least from what I've tested so far), but I cannot think of a way to include memorization. By memorization, I mean that I am trying to make it so that the algorithm will never compute the value for any game state more than once.

I am guessing a good way to do this would be to a map. The keys would be the game states, and the values would be the value of that game state (an int). I was planning on storing the game states in the map along with their values as they came up, but I ran into a problem.

The problem is this: My engine is templated as <class Game, class State>, and any game that uses this engine must conform to an interface defined by the engine. The state of the game will be a struct that contains various information about that move, usually at least the game board and the player who can make that move. Since the game states are structs, and there is no == operator for a struct, I do not know how to detect if a game state has already had its value computed. This is a generic engine, so the engine cannot know anything about the game, so I cannot check specific struct properties.

To help clarify, here is the code so far (thrown together as of now, but it works) for the engine:

#include <iostream>
#include <vector>
#include <map>
using namespace std;

template<class Game, class State>
class Engine {
      
      public:
      
      Game game;
      
      /**
      * Find the value of a game state for min that will result from
      * playing a perfect game from that state
      *
      * @param state The current state of the game
      * @return The value of the last move in the perfect game
      */
      int min (State state) {
          // A vector of all possible states from state
          vector<State> states = game.getMoves(state);
          // Is this state a terminal state?
          if (game.isGameOver(state)) {
             return game.stateValue(state);
          }
          // Not a terminal state
          else {
             int bestVal;
             for (int i = 0; i < states.size(); i++) {
                 // Where would min move?
                 int currentVal = max(states[i]);
                 // We want to corner max, which means min-ing max's value as 
                 // much as possible
                 if (currentVal < bestVal || i == 0) {
                    bestVal = currentVal;
                 }
             }
             return bestVal;
          } // terminal else
      }
      
      /**
      * Find the valuue of a game state for max that will result from
      * playing a perfect game from that state
      *
      * @param state The current state of the game
      * @return The value of the last move in the perfect game
      */
      int max (State state) {
          // A vector of all possible states from state
          vector<State> states = game.getMoves(state);
          // Is this state a terminal state?
          if (game.isGameOver(state)) {
             return game.stateValue(state);
          }
          // Not a terminal state
          else {
             int bestVal;
             for (int i = 0; i < states.size(); i++) {
                 // Where would min move?
                 int currentVal = min(states[i]);
                 // We want to corner min, which means maxing min's value as 
                 // much as possible
                 if (currentVal > bestVal || i == 0) {
                    bestVal = currentVal;
                 }
             }
             return bestVal;
          } // terminal else
      }
      
      /**
      * Returns the best move from a given state for either player.
      * Assume the player is Max. It really doesn't matter. This is
      * Just a utility function that acts as a top level of recurrsion
      *
      * @param currentState The current state of the game
      * @return The best possible move
      */
      State minimax (State currentState) {
            State retState; // The return state
            // For each possible move from this move...
            vector<State> states = game.getMoves(currentState);
            int bestVal;
            for (int i = 0; i < states.size(); i++) {
                // Get the move with the highest value (because we're max)
                int currentVal = max(states[i]);
                if (currentVal > bestVal || i == 0) {
                   retState = states[i];
                   bestVal = currentVal;
                }
            }
            return retState;
      }
};

Here is an example of class/struct definitions for a game that uses the engine (takeaway):

struct takeAwayState {
       int player; // the player who can make this move. 1 for min. 2 for max.
       int coinsLeft;
};

class takeAwayGame {
public:
   vector<takeAwayState> getMoves(takeAwayState);
   int stateValue(takeAwayState);
   takeAwayState playerMove(takeAwayState);
   void printMove (takeAwayState,takeAwayState);
   bool isGameOver (takeAwayState);
   void play (takeAwayState currentState, bool playOption);
};

The engine would be used in this case as:

Engine<takeAwayGame, takeAwayState> theEngine;
takeAwayState nextMove = theEngine.minimax(currentState);

I don't want the exact answer, just an idea to get me started . Any help would be greatly appreciated.

Thanks,
Alex

[pm_kirkham]

In order to use a std::map with arbitrary types, you supply a predicate which defines the ordering of the keys to use for the map. You could add an extra template parameter to capture the type of the ordering, as the stl does.