5
\$\begingroup\$

I'm working on a simple General Game Playing AI library. The idea is that it should work with almost any kind of game, with a minimum of configuration. At the moment, I have it working on 2 player turn based games like Tic-Tac-Toe, Connect 4 and chess. And it works quite well. It uses the Monte Carlo Tree Search algorithm which technically doesn't require any domain knowledge.

I'm only getting started with this library and plan to add support for many other types of games. To make future code modification as painless as possible I'd really like for the architecture to be as SOLID as possible. Any suggestions on ways to improve the architecture and on the use of design patterns will be appreciated. I'm also looking for some feedback on my name choices for variables, classes, properties, methods etc. Finally, I would love to know what you think of the public API (see use case at the bottom) and if you think it could be improved.

macao.ts

import { loopFor, spliceRandom } from "./utils";
import { MCTSNode, MCTSState } from "./classes";

export interface Playerwise {
  player: number;
}

export interface GenerateActions<S extends Playerwise, A> {
  (state: S): A[];
}
export interface ApplyAction<S extends Playerwise, A> {
  (state: S, action: A): S;
}
export interface StateIsTerminal<S extends Playerwise> {
  (state: S): boolean;
}
export interface CalculateReward<S extends Playerwise> {
  (state: S, player: number): number;
}

export default class Macao<S extends Playerwise, A> {
  private map: Map<string | number, MCTSState<S, A>> = new Map();

  private generateActions: GenerateActions<S, A>;
  private applyAction: ApplyAction<S, A>;
  private stateIsTerminal: StateIsTerminal<S>;
  private calculateReward: CalculateReward<S>;

  private duration: number;
  private explorationParam: number = 1.414;

  constructor(
    funcs: {
      generateActions: GenerateActions<S, A>;
      applyAction: ApplyAction<S, A>;
      stateIsTerminal: StateIsTerminal<S>;
      calculateReward: CalculateReward<S>;
    },
    config: {
      duration: number;
      explorationParam?: number;
    }
  ) {
    this.generateActions = funcs.generateActions;
    this.applyAction = funcs.applyAction;
    this.stateIsTerminal = funcs.stateIsTerminal;
    this.calculateReward = funcs.calculateReward;

    this.duration = config.duration;
    this.explorationParam = config.explorationParam || this.explorationParam;
  }

  public getAction(state: S): A {
    const rootNode = this.createRootNode(state);
    loopFor(this.duration).seconds(() => {
      const node = this.select(rootNode);
      const score = this.simulate(node.mctsState.state);
      this.backPropagate_(node, score);
    });
    const bestChild = this.bestChild(rootNode, 0);
    if (!bestChild.action) {
      throw new Error("The selected node has no action associated with it.");
    }
    return bestChild.action;
  }

  private backPropagate_(node: MCTSNode<S, A> | undefined, score: number): void {
    while (node) {
      node.mctsState.visits++;
      node.mctsState.reward += score;
      score *= -1;
      node = node.parent;
    }
  }

  private bestChild(node: MCTSNode<S, A>, explorationParam: number = 1.414): MCTSNode<S, A> {
    const selectedNode = node.children.reduce((p, c) => {
      return this.UCB1(node.mctsState, p.mctsState, explorationParam) >
        this.UCB1(node.mctsState, c.mctsState, explorationParam)
        ? p
        : c;
    });

    return selectedNode;
  }

  private createRootNode(state: S): MCTSNode<S, A> {
    // Check to see if state is already in Map
    const stringifiedState = JSON.stringify(state);
    let mctsState = this.map.get(stringifiedState);
    // If it isn't, create a new MCTSState and store it in the map
    if (!mctsState) {
      mctsState = new MCTSState(state);
      this.map.set(stringifiedState, mctsState);
    }
    // Create new MCTSNode
    const node = new MCTSNode(mctsState, this.generateActions(state));
    return node;
  }

  private expand(node: MCTSNode<S, A>): MCTSNode<S, A> {
    const action = spliceRandom(node.possibleActionsLeftToExpand);
    const state = this.applyAction(node.mctsState.state, action);
    // Check to see if state is already in Map
    const stringifiedState = JSON.stringify(state);
    let mctsState = this.map.get(stringifiedState);
    // If it isn't, create a new MCTSState and store it in the map
    if (!mctsState) {
      mctsState = new MCTSState(state);
      this.map.set(stringifiedState, mctsState);
    }
    const child = node.addChild(mctsState, this.generateActions(state), action);
    return child;
  }

  private select(node: MCTSNode<S, A>): MCTSNode<S, A> {
    while (!this.stateIsTerminal(node.mctsState.state)) {
      if (node.isNotFullyExpanded()) {
        return this.expand(node);
      }
      node = this.bestChild(node, this.explorationParam);
    }
    return node;
  }

  private simulate(state: S): number {
    const player = state.player;
    while (!this.stateIsTerminal(state)) {
      // Generate possible actions
      const actions = this.generateActions(state);

      // Select an action at random
      const action = spliceRandom(actions);

      // Apply action and create new state
      state = this.applyAction(state, action);
    }
    return this.calculateReward(state, player);
  }

  private UCB1(parent: MCTSState<S, A>, child: MCTSState<S, A>, explorationParam: number): number {
    const exploitationTerm = child.reward / child.visits;
    const explorationTerm = Math.sqrt(Math.log(parent.visits) / child.visits);
    return exploitationTerm + explorationParam * explorationTerm;
  }
}

classes.ts

export class MCTSNode<S, A> {
  readonly possibleActionsLeftToExpand: A[];
  readonly children: MCTSNode<S, A>[] = [];
  constructor(readonly mctsState: MCTSState<S, A>, possibleActions: A[], readonly parent?: MCTSNode<S,A>, readonly action?: A) {
    this.possibleActionsLeftToExpand = possibleActions;
  }

  addChild(mctsState: MCTSState<S, A>, possibleActions: A[], action: A): MCTSNode<S, A> {
    const node = new MCTSNode(mctsState, possibleActions, this, action);
    this.children.push(node);
    return node;
  }

  isNotFullyExpanded(): boolean {
    return this.possibleActionsLeftToExpand.length > 0;
  }
}

export class MCTSState<S, A> {
  reward: number = 0;
  visits: number = 0;
  constructor(readonly state: S) { }
}  

utils.ts

export const getRandomIntInclusive = (min: number, max: number): number => {
  min = Math.ceil(min);
  max = Math.floor(max);
  return Math.floor(Math.random() * (max - min + 1)) + min; // The maximum is inclusive and the minimum is inclusive
};

export const spliceRandom = <T>(array: T[]): T => {
  const index = getRandomIntInclusive(0, array.length - 1);
  return array.splice(index, 1)[0];
};

export const loopFor = (time: number) => {
  return {
    seconds: (callback: () => any) => {
      const start = performance.now();
      const t = time * 1000;
      while (performance.now() - start < t) {
        callback();
      }
    },
    turns: (callback: () => any) => {
      while (time > 0) {
        callback();
        time--;
      }
    }
  };
};  

And here is the kind of code a user of the library would write:

import Macao from 'macao'

const generateActions = (state) => {
  // Implementation details
}
const applyAction = (state, move) => {
  // Implementation details
}
const stateIsTerminal = (state) => {
  // Implementation details
}
const calculateReward = (state, player) => {
  // Implementation details
}

const funcs = {
  generateActions,
  applyAction,
  stateIsTerminal,
  calculateReward
}

macao = new Macao(funcs, {duration: 0.1});

// Game setup code
...
const state = {} //some object containing the game state;

while (!stateIsTerminal(state)) {  
  const bestMove = macao.getAction(state);
  state = applyAction(state, bestMove);
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.