///////////////////////////////////////////////////////////////
// Game.java
// abstrakte Spielstrategie für symmetrische Zweipersonenspiele
//

import java.awt.*;

class MoveInfo {
  public MoveInfo (int index, int value) {
    this.index = index;
    this.value = value;
  }
  public int index;
  public int value;
}

abstract class GameState {
  public abstract int value ();
  public abstract int nMoves ();
  public abstract GameState move (int i);

  public GameState bestMove (int depth) {
    MoveInfo m = alphaBetaMax (depth, Integer.MIN_VALUE, Integer.MAX_VALUE);
    return move (m.index);
  }

  private MoveInfo alphaBetaMax (int depth, int alpha, int beta) {
    int n = nMoves ();
    if (n == 0 || depth <= 0) // Blattbewertung
      return new MoveInfo (0, value ());
    MoveInfo best = new MoveInfo (0, alpha);
    for (int i=0; i<n; i++) {
      MoveInfo newMove = move(i).alphaBetaMin (depth-1, best.value, beta);
      if (newMove.value > best.value) {
        best.index = i;
        best.value = newMove.value;
      }
      if (best.value >= beta) {
        best.index = i;
        return best;
      }
    }
    return best;
  }

  private MoveInfo alphaBetaMin (int depth, int alpha, int beta) {
    int n = nMoves ();
    if (n == 0 || depth <= 0) // Blattbewertung
      return new MoveInfo (0, value ());
    MoveInfo best = new MoveInfo (0, beta);
    for (int i=0; i<n; i++) {
      MoveInfo newMove = move(i).alphaBetaMax (depth-1, alpha, best.value);
      if (newMove.value < best.value) {
        best.index = i;
        best.value = newMove.value;
      }
      if (best.value <= alpha) {
        best.index = i;
        return best;
      }
    }
    return best;
  }
}