Milena hat mit ihrer Lösung die Code Competition Kampf gegen Mühlen gewonnen herzlichen Glückwunsch!Milenas 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 Milenas 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 Milenas 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 Milenas 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 => { 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>> orderedResults = children.GroupBy(node => node.AlphaBetaValue); orderedResults = orderedResults.OrderByDescending(x => x.Key); return orderedResults.FirstOrDefault().ToList(); } } } Der Beitrag Milena gewinnt Code Competition Kampf gegen Mühlen erschien zuerst auf IT-Talents.de.
Herzlichen Glückwunsch an Leonardo, Leon und Lukas Bei der Code Competition Der Paketbote haben wir Euch aufgerufen, ein kleines Spiel zu programmieren. Viele Talente sind dem Ruf gefolgt und haben tolle Lösungen eingereicht. Die Gewinner stehen nun fe
zum Artikel gehenBenedikt gewinnt Code Competition und 500€ Preisgeld! Benedikt hat seine Lösung zur Code Competition Kampf gegen Mühlen in JavaScript entwickelt und dabei eine ganze Menge gelernt. Seine Lösung hat überzeugt und Benedikt den ersten Platz eingebracht h
zum Artikel gehenHerzlichen Glückwunsch an Daniel zu 400€ Preisgeld! Daniel studiert Medieninformatik und hat bereits erste Erfahrung mit der Entwicklung eigener Spiele sammeln können. Mit seiner Lösung und der starken KI konnte er überzeugen und hat den zweiten Plat
zum Artikel gehenHerzlichen Glückwunsch und Danke für viele spannende Lösungen! Die Auswertung der Code Competition 06/2017 Chatbot und maschinelles Lernen ist ausgewertet. Vielen Dank für die wie immer sehr spannenden Lösungen.Und herzlichen Glückwunsch an die Gewinne
zum Artikel gehenMit einer tollen Lösung des Rucksackproblems in Java. Der 27jährige Student der Angewandten Informatik in Duisburg gewinnt die Code Competition und erhält 400€ Förderung. Herzlichen Glückwunsch! IT-Talents: Hallo James, herzlichen Glückwunsch zu Dei
zum Artikel gehen