Milena gewinnt Code Competition “Kampf gegen Mühlen”

Schau Dir jetzt Milena’s Code des Alpha-Beta-Pruning-Algorithmus an:

using Mills.Game.BoardComponents;
using Mills.Game;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Threading.Tasks;

namespace Mills.Game.Players.AI
{

    /// <summary>
    /// Alpha-beta pruning extends the minimax algorithm and is commonly used for two-player games. See
    /// <a href="https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning">Wikipedia</a>
    /// </summary>
    public class AlphaBetaPruning
    {
        /// <summary>
        /// Count of visited nodes.
        /// </summary>
        private static int NodeCount;

        /// <summary>
        /// Calculates the value of the specified node.
        /// </summary>
        /// <param name="node">The Node of which the value is to be calculated
        /// <param name="depth">The depth for the tree
        /// <param name="alpha">Currently known max value
        /// <param name="beta">Currently known min value
        /// <param name="maximizingPlayer">Whether the current player is maximizing
        /// <returns>The Alpha-beta value of this node.</returns>
        public static int AlphaBeta(TreeNode node, int depth, int alpha, int beta, bool maximizingPlayer)
        {
            // count visited node
            NodeCount++;

            // Leaf
            if (depth == 0 || node.IsLeaf)            
                return node.HeuristicValue;            

            List<treenode> nodes = node.GetChildNodes();

            // Maximizing
            if (maximizingPlayer)
            {
                // Sorting improves performance because more sub-trees can be cut off
                nodes.Sort(TreeNode.CompareByHeuristicDescending);
                int result = int.MinValue;
                foreach(TreeNode child in nodes)
                {
                    result = Math.Max(result, AlphaBeta(child, depth - 1, alpha, beta, false));
                    alpha = Math.Max(alpha, result);
                    if (beta 
        /// Returns the optimal move to answer the specified GameState.
        /// 
        /// <param name="gameState">The current GameState on which to react
        /// <param name="depth">The search depth for finding the optimal move
        /// <returns>The optimal move as a Sequence of PositionIDs to select.</returns>
        public static Stack<positionid> CalculateNextMoves(GameState gameState, int depth)
        {
            NodeCount = 0;

            // Node of current game state
            TreeNode root = new TreeNode(false) { GameState = gameState };

            // List of all possible follow-up game states
            List<treenode> children = root.GetChildNodes();

            // happens if no moves are possible
            if (children == null)
                return null;

            children.Sort(TreeNode.CompareByHeuristicDescending);

            Stopwatch watch = new Stopwatch();
            watch.Start();

            // Calculate the Alpha-beta value for each child
            Parallel.ForEach( children,
                child =&gt; {
                    child.AlphaBetaValue = AlphaBetaPruning.AlphaBeta(child, depth - 1, int.MinValue, int.MaxValue, false);
                }
            );
            watch.Stop();

            // Thought this might interest you ;-)
            Console.WriteLine("It took the algorithm " + watch.ElapsedMilliseconds + "ms to traverse " + NodeCount + " Nodes.");
            Console.WriteLine("Search depth was " + depth + ".");

            // Select the best option
            List <treenode> candidates = GetListOfCandidates(children);
            candidates.Sort(TreeNode.CompareByHeuristicDescending);
            TreeNode result = candidates.FirstOrDefault();
            return new Stack<positionid>(result.Moves);
        }

        /// <summary>
        /// Returns the TreeNodes with maximal Alpha-beta value
        /// </summary>
        /// <param name="children">The list from which to select
        /// <returns>the TreeNodes with maximal Alpha-beta value</returns>
        private static List<treenode> GetListOfCandidates(List<treenode> children)
        {
            IEnumerable<igrouping treenode>&gt; orderedResults = children.GroupBy(node =&gt; node.AlphaBetaValue);
            orderedResults = orderedResults.OrderByDescending(x =&gt; x.Key);
            return orderedResults.FirstOrDefault().ToList(); 
        }

    }
}