Milena hat mit ihrer Lösung die Code Competition “Kampf gegen Mühlen” gewonnen – herzlichen Glückwunsch!
Milena’s Programm konnte durch verschiedene Spielmodi und eine durchdachte KI überzeugen.
IT-Talents: Hallo Milena, herzlichen Glückwunsch zu Platz 1 bei der Code Competition „Kampf gegen Mühlen“! Erzähl den anderen IT-Talenten doch kurz etwas über Dich.
Milena: Hallo und danke 🙂 Ich studiere Informatik am Karlsruher Institut für Technologie und bin noch 2 Semester von meinem Bachelor entfernt, auf den sicher der Master folgen wird. Nebenher arbeite ich in der Software-Entwicklung bei PTV (Logistik- und Traffic-Software) und die Zeit, die dann noch übrig bleibt, verbringe ich mit Musik, Lesen, moderner Japanischer Kultur und natürlich noch mehr Programmieren…
IT-Talents: Was hat Dich motiviert, an der Competition teilzunehmen und wie bist Du auf den Wettbewerb aufmerksam geworden?
Milena: Ich habe schon etwas länger einen Account bei IT-Talents, war aber eher ein Lurker. Als ich die Info-Mail für diesen Wettbewerb erhielt, hatte meine vorlesungs- und prüfungsfreie Zeit gerade begonnen, ich wollte schon länger mal etwas mit C# und WPF machen und das Thema fand ich auch interessant, also hat einfach alles gepasst.
Screenshot aus Milena’s Programm. So sieht der Startbildschirm aus.
IT-Talents: Wie bist Du an die Lösung der Aufgabenstellung herangegangen?
Milena: Zu allererst hab ich mir natürlich einige Wikipedia-Artikel zu Mühle und Spieltheorie durchgelesen. Dann habe ich mir die grobe Struktur überlegt und dazu ein paar UML-Diagramme gezeichnet. Ich habe einige Design-Patterns, die mir sinnvoll erschienen und die ich ausprobieren wollte, verwendet. Vor allem das Strategy-Pattern für das Auswählen des nächsten Zuges eines Spielers (ggf. durch die AI) kam mir zugute, dadurch konnte ich am Schluss mit wenigen Handgriffen beliebig viele Computer-Gegner einbauen. Die Implementierung war ein eher lockeres Top-Down und ich hab auch viel herumgespielt.
Screenshot aus Milena’s Programm. Hier spielt ein Computergegner gegen einen anderen.
IT-Talents: Hattest Du schon Erfahrung mit der Entwicklung von Künstlicher Intelligenz und passenden Algorithmen?
Ein bisschen. Den Algorithmus (Minimax-Algorithmus mit Alpha-Beta-Pruning), den ich für meine AIs verwendet habe, kannte ich bereits aus dem Studium. Deswegen lag es für mich nahe, diesen zu verwenden, obwohl es für Mühle auch noch effizientere Algorithmen gibt. Weil Minimax sich einfach parametrisieren lässt, konnte ich durch die Änderung der Suchtiefe unterschiedlich starke AIs anbieten. Ich finde Künstliche Intelligenz ein sehr interessantes Thema und werde mich im Master in diese Richtung weiter vertiefen. Natürlich konnte ich es mir auch nicht verkneifen, zusätzlich einen Computer-Gegner einzubauen, der zufällig seinen nächsten Zug wählt, aber intelligent ist das ja nicht.
IT-Talents: Welche Probleme sind bei der Entwicklung der Software aufgekommen? Wie lange hat die Entwicklung gedauert?
Milena: Richtige Probleme hielten sich bei mir in Grenzen. Ich hätte meine AIs gerne noch etwas schneller gemacht – das war aber eher eine Frage des Zeitmanagements.
Ich habe leider nicht Buch darüber geführt, wie viel Zeit ich dafür verwendet habe, zwischendrin habe ich mich auch allgemein in C# und WPF eingearbeitet. Beim Überschlagen der Zeit, die ich tatsächlich nur für das Programm verwendet habe, komme ich auf 100-150h. Nächstes Mal werde ich das protokollieren, es würde mich nämlich selbst interessieren…
IT-Talents: Und was hast Du durch die Entwicklung gelernt?
Milena: Eine ganze Menge! Das war mein erstes größeres Programm, bei dem ich von Top bis Bottom alles selbst geschrieben habe und ich hatte davor nur wenig mit C# und noch nichts mit WPF oder GUI-Design gemacht. Bei der Gelegenheit habe ich mich in einiges eingelesen.
IT-Talents: Das hört sich ja echt super an! Zu guter Letzt: Was würdest Du Dir thematisch gerne einmal als Code Competition wünschen?
Milena: Ich fände es super, wenn man für ein Spiel mit von euch gegebener API eine AI schreibt, die dann gegen die AIs der anderen Teilnehmer antritt. Also so was in die Richtung Battlecode vom MIT.
IT-Talents: Vielen Dank für Deine Teilnahme, das Interview und viel Spaß mit Deinem Gewinn 😉
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 { /// /// Alpha-beta pruning extends the minimax algorithm and is commonly used for two-player games. See /// Wikipedia /// public class AlphaBetaPruning { /// /// Count of visited nodes. /// private static int NodeCount; /// /// Calculates the value of the specified node. /// /// The Node of which the value is to be calculated /// The depth for the tree /// Currently known max value /// Currently known min value /// Whether the current player is maximizing /// The Alpha-beta value of this node. 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 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. /// /// The current GameState on which to react /// The search depth for finding the optimal move /// The optimal move as a Sequence of PositionIDs to select. public static Stack 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 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 => { 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 candidates = GetListOfCandidates(children); candidates.Sort(TreeNode.CompareByHeuristicDescending); TreeNode result = candidates.FirstOrDefault(); return new Stack(result.Moves); } /// /// Returns the TreeNodes with maximal Alpha-beta value /// /// The list from which to select /// the TreeNodes with maximal Alpha-beta value private static List GetListOfCandidates(List children) { IEnumerable> orderedResults = children.GroupBy(node => node.AlphaBetaValue); orderedResults = orderedResults.OrderByDescending(x => x.Key); return orderedResults.FirstOrDefault().ToList(); } } }