nouseforname.de

Umsetzung einer zweiseitigen KI mit MiniMax

using System;
using System.Collections.Generic;

namespace TicTacTo
{
  /// <summary>
  ///  TicTacToe game methods
  /// </summary>
  public class TicTacToe
  {
    private const int MaxGridSpaces = 9;
    private int _turnCounter = 0;

    public List<GridSpace> ListGridSpaces { set; get; } = new List<GridSpace>(MaxGridSpaces);
    public int[] CounterWins { set; get; } = { 0, 0 };
    public int CounterDraws { set; get; } = 0;
    public int CounterTotal { get { return CounterDraws + CounterWins[0] + CounterWins[1]; } }
    public EnumScore EnumScore { set; get; } = EnumScore.NextTurn;
    public bool IsHumanPlayer { set; get; } = true;

    public TicTacToe()
    {
      Init();
    }

    /// <summary>
    ///  Init the game grid
    /// </summary>
    public void Init()
    {
      ListGridSpaces.Clear();
      for (var i = 0; i < MaxGridSpaces; i++)
        ListGridSpaces.Add(new GridSpace(i));

      _turnCounter = 0;

      IsHumanPlayer = StartScreen.GameMode == EnumGameMode.MultiPlayer ||
                      (StartScreen.GameMode != EnumGameMode.Simulation && CounterTotal % 2 == 0);
    }

    /// <summary>
    /// Get current player index / swap it each round
    /// </summary>
    /// <returns>int</returns>
    public int GetPlayerIndex()
    {
      return ((_turnCounter % 2) + (CounterTotal % 2)) % 2;
    }

    /// <summary>
    /// Returns if there are moves left
    /// </summary>
    /// <param name="board"></param>
    /// <returns></returns>
    private bool IsMovesLeft(List<GridSpace> board)
    {
      foreach (var space in board)
      {
        if (space.IsPlayed)
          continue;

        return true;
      }

      return false;
    }

    /// <summary>
    /// Do a players turn
    /// </summary>
    /// <param name="index"></param>
    /// <returns>EnumScore</returns>
    public EnumScore DoTurn(int index)
    {
      if (StartScreen.GameMode == EnumGameMode.SinglePlayer)
        IsHumanPlayer = !IsHumanPlayer;

      var player = GetPlayerIndex();
      SetSpace(index, false);

      if (Evaluate(ListGridSpaces))
      {
        CounterWins[player]++;
        return (EnumScore)player;
      }

      if (!IsMovesLeft(ListGridSpaces))
      {
        CounterDraws++;
        return EnumScore.Draw;
      }

      return EnumScore.NextTurn;
    }

    /// <summary>
    /// Set grid space to player or reset in real Game Board
    /// </summary>
    /// <param name="index"></param>
    /// <param name="reset"></param>
    public void SetSpace(int index, bool reset)
    {
      ListGridSpaces[index].SetSpace(reset ? EnumPlayerName._ : (EnumPlayerName)GetPlayerIndex());
      _turnCounter = !reset ? _turnCounter + 1 : _turnCounter - 1;
    }

    /// <summary>
    ///  evaluate if a player won the game
    /// </summary>
    /// <param name="board"></param>
    /// <returns>bool</returns>
    private bool Evaluate(List<GridSpace> board)
    {
      // game need 5 turns to have a winner at least
      if (_turnCounter < 5)
        return false;

      return (board[0].IsPlayed && board[0].PlayerName == board[1].PlayerName && board[0].PlayerName == board[2].PlayerName) ||
             (board[3].IsPlayed && board[3].PlayerName == board[4].PlayerName && board[3].PlayerName == board[5].PlayerName) ||
             (board[6].IsPlayed && board[6].PlayerName == board[7].PlayerName && board[6].PlayerName == board[8].PlayerName) ||
             (board[0].IsPlayed && board[0].PlayerName == board[3].PlayerName && board[0].PlayerName == board[6].PlayerName) ||
             (board[1].IsPlayed && board[1].PlayerName == board[4].PlayerName && board[1].PlayerName == board[7].PlayerName) ||
             (board[2].IsPlayed && board[2].PlayerName == board[5].PlayerName && board[2].PlayerName == board[8].PlayerName) ||
             (board[0].IsPlayed && board[0].PlayerName == board[4].PlayerName && board[0].PlayerName == board[8].PlayerName) ||
             (board[2].IsPlayed && board[2].PlayerName == board[4].PlayerName && board[2].PlayerName == board[6].PlayerName);
    }

    /// <summary>
    ///  get remaining playable fields list
    /// </summary>
    /// <returns>List<int></int></returns>
    private List<int> GetRemainingIndexList()
    {
      var result = new List<int>();
      foreach (var space in ListGridSpaces)
      {
        if (space.IsPlayed)
          continue;

        result.Add(space.Index);
      }

      return result;
    }

    /// <summary>
    ///  Get next index according to Game mode
    /// </summary>
    /// <returns>int</returns>
    public int GetNextIndex()
    {
      switch (StartScreen.GameDifficulty)
      {
        case EnumGameDifficulty.Easy:
          var list = GetRemainingIndexList();
          return list[UnityEngine.Random.Range(0, list.Count)];

        case EnumGameDifficulty.Hard:

          // if center is not used yet, use it
          if (GetRemainingIndexList().Count == 9 || !ListGridSpaces[4].IsPlayed)
            return 4;

          return FindBestMove();
      }
      return -99;
    }

    /// <summary>
    ///  Find next best move by using MiniMax
    /// </summary>
    /// <returns>int</returns>
    public int FindBestMove()
    {
      var listMoves = new List<Move>();
      var bestScore = GetPlayerIndex() == 0 ? int.MinValue : int.MaxValue;
      var bestMove = -1;
      var board = new List<GridSpace>(ListGridSpaces);
      foreach (var space in board)
      {
        if (space.IsPlayed)
          continue;

        space.SetSpace((EnumPlayerName)GetPlayerIndex());
        _turnCounter++;
        int score = MiniMax(board, 0, GetPlayerIndex() == 0, int.MinValue, int.MaxValue);
        space.SetSpace(EnumPlayerName._);
        _turnCounter--;

        // find bext score
        if ((GetPlayerIndex() == 0 && score >= bestScore) || (GetPlayerIndex() == 1 && score <= bestScore))
        {
          bestScore = score;
          bestMove = space.Index;
          listMoves.Add(new Move(score, space.Index));
        }
      }

      // if only one result exist
      if (listMoves.Count == 1)
        return bestMove;

      return RandomizeBestMove(listMoves, bestScore);
    }

    /// <summary>
    ///  miniMax algorythm to find best next index recursivly
    /// </summary>
    /// <param name="board"></param>
    /// <param name="depth"></param>
    /// <param name="isMax"></param>
    /// <returns></returns>
    private int MiniMax(List<GridSpace> board, int depth, bool isMax, int alpha, int beta)
    {
      if (Evaluate(board))
        return GetPlayerIndex() == 0 ? -10 : 10;

      if (!IsMovesLeft(board))
        return 0;

      int bestScore = isMax ? int.MinValue : int.MaxValue;
      foreach (var space in board)
      {
        if (space.IsPlayed)
          continue;

        space.SetSpace((EnumPlayerName)GetPlayerIndex());
        _turnCounter++;

        bestScore = isMax ?
          Math.Max(bestScore, MiniMax(board, depth + 1, !isMax, alpha, beta)) :
          Math.Min(bestScore, MiniMax(board, depth + 1, !isMax, alpha, beta));

        space.SetSpace(EnumPlayerName._);
        _turnCounter--;

        if (isMax) alpha = Math.Max(alpha, bestScore);
        else beta = Math.Min(beta, bestScore);

        if (beta <= alpha)
          break;
      }
      return isMax ? bestScore - depth : bestScore + depth;
    }

    /// <summary>
    ///  Randomize result of moves
    /// </summary>
    /// <param name="moves"></param>
    /// <returns></returns>
    private int RandomizeBestMove(List<Move> moves, int best)
    {
      // randomize if score is same
      var listBestMoves = new List<int>();
      foreach (var move in moves)
      {
        if (move.Score != best)
          continue;

        listBestMoves.Add(move.Index);
      }

      return listBestMoves[UnityEngine.Random.Range(0, listBestMoves.Count)];
    }
  }
}