I am programming an Nine-Mens-Morris game in WPF and it is almost finished. But my Alpha-Beta-AI is a little bit too easy. I want to implement a strategy for the AI. The AI should win as good as always. I don't want to increase the search tree depth more than 6 because it takes too long to calculate.
Sorry if my English isn't that good.
Here is the source code of the Alpha-Beta AI
What I have tried:
using Młynek.Model;
using Młynek.Utils;
using System;
using System.Diagnostics;
using System.Threading.Tasks;
namespace Młynek.Players
{
class AlfaBetaSpieler : ISpieler
{
private FieldState _color;
private IEvaluateGameState _evaluator;
private AIHelper _aiHelper;
private Spiel _game;
private Spielzug _pendingCapture;
private long _nodesCount;
private int _depth;
public bool IsHuman => false;
public string TypeName => "AlphaBeta";
public AlfaBetaSpieler(FieldState color, int depth, GameStateEvaluator evaluator)
{
_color = color;
_evaluator = evaluator;
_depth = depth;
_aiHelper = new AIHelper();
}
public async Task<Spielzug> AIMove(Spiel game)
{
_nodesCount = 0;
Stopwatch timer = Stopwatch.StartNew();
Spielzug nextMove = await Task.Run(() =>
{
_game = game.Duplicate();
return AlfaBeta();
});
if (nextMove.Capture >= 0) _pendingCapture = new Spielzug(_color, nextMove.Capture);
timer.Stop();
nextMove.Time = timer.ElapsedMilliseconds;
nextMove.NodesVisited = _nodesCount;
return nextMove;
}
public Spielzug AICapture(Spiel game)
{
if (!_pendingCapture.IsValid()) throw new InvalidOperationException();
Spielzug capture = _pendingCapture;
_pendingCapture = new Spielzug();
return capture;
}
public Spielzug AlfaBeta()
{
int depth = _game.GetRound() == 2 ? _depth : 3;
Spielzug nextMove = AlfaBetaRecursion(depth, float.MinValue, float.MaxValue).Item2;
_game = null;
return nextMove;
}
public (float, Spielzug) AlfaBetaRecursion(int depth, float alfa, float beta)
{
_nodesCount++;
if (depth == 0 || _game.GameEnded)
{
return (_evaluator.EvaluateGameState(_game, _color), new Spielzug(FieldState.Empty));
}
Spielzug[] possibleMoves = _aiHelper.GetAvaiableMoves(_game);
if (possibleMoves.Length == 0)
{
Spielzug giveUp = new Spielzug(_game.NextPlayer);
_game.MakeMove(giveUp);
return ((AlfaBetaRecursion(depth - 1, alfa, beta).Item1, giveUp));
}
if (_game.NextPlayer == _color)
{
var max = (Item1: float.MinValue, new Spielzug(FieldState.Empty));
for (int i = 0; i < possibleMoves.Length; i++)
{
Spielzug move = possibleMoves[i];
_game.MakeMove(move);
if (move.CreatesMill) _game.Capture(new Spielzug(move.Player, move.Capture));
if (max.Item1 >= alfa) alfa = max.Item1;
var eval = ((AlfaBetaRecursion(depth - 1, alfa, beta).Item1, move));
_game.Undo();
if (eval.Item1 >= beta) return eval;
if (eval.Item1 >= max.Item1) max = eval;
}
return max;
}
else
{
var min = (Item1: float.MaxValue, new Spielzug(FieldState.Empty));
for (int i = 0; i < possibleMoves.Length; i++)
{
Spielzug move = possibleMoves[i];
_game.MakeMove(move);
if (move.CreatesMill) _game.Capture(new Spielzug(move.Player, move.Capture));
if (min.Item1 <= beta) beta = min.Item1;
var eval = ((AlfaBetaRecursion(depth - 1, alfa, beta).Item1, move));
_game.Undo();
if (eval.Item1 <= alfa) return eval;
if (eval.Item1 <= min.Item1) min = eval;
}
return min;
}
}
public void Move(Spiel game)
{
throw new NotImplementedException();
}
public void Capture(Spiel game)
{
throw new NotImplementedException();
}
}
}
I am not so advanced but I have some knowledge of C#. So if you can help me, I would be really glad.