Click here to Skip to main content
15,905,967 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
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);

            //GIVE-UP PSEUDO MOVE
            if (possibleMoves.Length == 0)
            {
                Spielzug giveUp = new Spielzug(_game.NextPlayer);
                _game.MakeMove(giveUp);
                return ((AlfaBetaRecursion(depth - 1, alfa, beta).Item1, giveUp));
            }

            // MAXIMIZING PLAYER
            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;
            }
            // MINIMIZING PLAYER
            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.
Posted

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900