Eine weitere Geschichte aus meiner Studienzeit. Seid gewarnt langen Artikel.
Engineering Colleges in Kerala verlangen, Studenten, Kurse einen Mini-Projekt im dritten Jahr ihrer Informatik und Ingenieurwissenschaften. Dies ist zusätzlich zu den wichtigsten Vorhaben, das natürlich ist das der zu eingereichten im letzten Jahr.
Zwei meiner Klassenkameraden - Praveen Kumar (die in unseren Kreisen gilt gleich Jon Skeet ), Philip und ich bildeten unser Team für dieses Mini-Projekt. Wir waren sehr aufgeregt über dieses Projekt, dass wir Gespräche darüber begonnen viel früher als der offizielle Projektstart Zeit. Nach vielen Debatten, die wir spät in der Nacht beschlossen, ein Schach-Programm zu entwickeln.
Drei von uns waren Sharing einem gemieteten Haus nahe College, und wir pflegten zu 1 entwickeln Software-Tools für verschiedene Zwecke #. Der wichtigste Punkt hierbei ist, dass wir diese Programme - warten Sie - Visual Basic 6 entwickelt.
Wir waren sehr komfortabel in Visual Basic, und da ist es sehr einfach, Schach zu entwickeln, ein gutes UI in Visual Basic , begannen wir den Aufbau einer Prototyp der Anwendung in VB6. Wir dachten, dass, sobald die grundlegende Logik ist fertig und arbeiten, würden wir Portierung auf eine bessere und schnellere Sprache. Leider arbeiteten wir an den Code für sehr lange und hart, dass die Code-Basis größer und mehr wuchs.
Testen des Programms war etwas knifflig. Die Alpha-Beta- Algorithmus wurde in einem betriebsbereiten Zustand und das Programm war die Erzeugung und macht einige grundlegende Schritte, aber wir waren vor zwei Problemen:
Problem 1: Wie können wir wissen, ob der Computer richtig gespielt hat? Es gibt keinen Weg, um wirklich sicherzustellen, dass der Computer die richtige Zug gespielt (für einen bestimmten Tiefe), weil wir selbst nicht wissen, die richtige Bewegung! Natürlich, wenn Sie sind ein guter Schachspieler können Sie herausfinden, ein guter Schachzug für eine bestimmte Position Bord, aber das löst nicht das Problem. Zunächst einmal können Sie nicht sicher sein, dass Ihr Umzug zu bewegen ist die beste. Was ist, wenn es besser geht, dass Sie gerade nicht sah? Zweitens weiß nicht genau Schachspieler denken wie ein Computer. Sie wissen nicht genau berechnen, die Bewegungen mit Hilfe eines Algorithmus. Einige ihrer Entscheidungen auf Intuition beruht.
Die besten Schachspieler kann nur bei einer Chess Position schauen und sehen, die 2-3 Zeilen des Spiels, dass sie zu analysieren, anstatt die Analyse aller 30 + zur Verfügung bewegt. Computer können das nicht. Die Computer sollten auf alle Züge aussehen zu entscheiden, ob die Linie zu spielen, um mehr Tiefe oder nicht analysieren. Die Menschen sind gut in Schach, während Computern gute Strategie in der Taktik sind. Dies bedeutet, dass ein Mensch kann nicht sagen, ob ein Computer ist das perfekte Spiel spielen (für einen bestimmten Tiefe) oder nicht.
Problem 2: Da unsere Umsetzung nicht vollständig ist und keine Optimierungen wurden zunächst gemacht, wäre der Computer nehmen sehr viel Zeit zu denken und machen den Umzug. Wir mussten etwas warten, wie 4 Minuten oder so auf jeden Zug aus dem Computer zu erhalten und es war die Aufnahme viel von unserer Entwicklungszeit. Überprüfung der Richtigkeit des Programms war, eine Menge Zeit in Anspruch nehmen.
Ein guter Weg, um Programm zu testen ein Schach ist es, sich gegen 2 spielen #. So würden wir bis spät in die Nacht und morgens, wenn wir aufs College zu gehen würden wir das Programm starten und es gegen sich selbst spielen Code. Wenn wir zurückkommen, wir würden auf die Logs schauen und sehen, was passiert ist. So viel wie aufgeregt wir waren, waren die Ergebnisse oft deprimierend. Die meiste Zeit des Spiels die) gehen in eine Schleife, wo jeder Spieler gespielt (vor und zurück bewegt gleichen . Der Grund dafür war, dass nach der Schach-AI # 3 Position gefunden der beste Zug für einen bestimmten Bord, spielt es gerade der Umzug ohne Berücksichtigung etwaiger weiterer Tatsachen, wie die Geschichte. Der beste Weg, um dieses Problem zu beheben ist, das Programm auf den Umzug der Geschichte zu betrachten in ihrer Entscheidung über die Stück zu bewegen erzählen.
Ein weiterer Grund für häufige Schleifen war, dass sowohl die Spieler im Spiel waren Stärke der gleichen (sie waren beide Züge voraus denken x). Um dies zu beheben und ein paar echte Ergebnisse, die wir machten sie in verschiedenen Stärken zu sehen. Einer der Spieler denkt, x Züge voraus, während der andere würde denken, x-2 oder so ähnlich. Diese Verbesserung hat uns einige echte Ergebnisse sehen. Als wir zurück kamen, um die Ergebnisse am Ende des Tages überprüfen, konnten wir einen der Spieler zu sehen schachmatt!
Wenn Sie in Computer sind, ist Schachprogrammierung eine der besten Möglichkeiten, um Spaß zu haben. Es gibt eine Menge Feinheiten bei der Umsetzung, so dass Sie das Programm wieder und wieder zwicken, um Verbesserungen zu erhalten. Die besten Schachspieler Programming Tutorial (für Anfänger) Ich habe treffen, ist das eine aus GameDev.net .
Ich erinnere mich an eine andere kleine Fehler wir konfrontiert waren. Hier ist, wie ein Computer Schach-Programm erfährt, den bestmöglichen Zug:
Finden Sie heraus, alle gültigen bewegt sich der Spieler zur Verfügung. Angenommen, Sie unterwegs gespielt und finden Sie heraus das neue Board Position. Jetzt in der neuen Position Bord aus der Sicht des Gegners anschauen und versuchen herauszufinden, was zu bewegen ist er wahrscheinlich zu machen. Wenn er sich bewegen lässt, was wird der neue Vorstandsbereich aussehen? Was bewegt Sie zu machen, um seinen Zug zu begegnen?
Sie können weiter gehen und iterativ tiefer und tiefer in diese Suche Baum # 4. Je tiefer Sie suchen, desto besser ist Ihre Entscheidung (move) werden. Für jede Position Bord der Algorithmus einen Wert zuweist. Die Gäste bestimmt, wie gut das Board Position ist. Wenn einer Ihrer Stücke eingefangen wird, verliert man so viel Gäste. Zum Beispiel, wenn Sie verlieren einen Bauern, verlieren Sie 1 Punkt.
Jetzt auf den folgenden Spielbaum aussehen. Blue ist ein Zug des Computers und rot, einen Umzug durch den Gegner. Die Zahlen geben die gewonnenen Punkte durch den Computer in jedem Schritt.
Zum Beispiel in der ersten Zeile zu spielen, kämpft der Computer gewinnt 5 Punkte in den ersten Schritt (wahrscheinlich durch die Erfassung ein Turm) und im Gegenzug den Gegner wieder durch 3 Punkte gewinnen (wahrscheinlich durch die Erfassung eines Bischofs / Ritter). Nun, wie Sie sich vielleicht erinnern, die Algorithmen sieht nur bei der Gesamtpunktzahl der Spieler am Ende jeder Zeile des Spiels. In beiden obigen Fällen, die insgesamt zu gewinnen durch den Computer ist 2 Punkte.
Wenn der Computer wählt zwischen diesen beiden Linien des Spiels nach dem Zufallsprinzip, sind Sie in für Ärger. Das Problem ist, dass der Computer nicht weiß, was geschieht, nachdem der letzte Zug in die Linie des Spiels. Dies bedeutet, dass, wenn Sie die erste Zeile des Spiels folgen Sie fast sicher sind zu gewinnen 2 Punkte nach der nächsten zwei Zügen, während in der zweiten Zeile spielen, werden Sie 3 Punkte nach der nächsten zwei Züge zu verlieren. Darf sein Sie können noch 5 Punkte später in das Spiel zu gewinnen, aber was ist, wenn nach zwei Züge mehr, wenn man weiter sehen kann in der Baumstruktur Sie feststellen, dass der Umzug Sie haben früher gesehen, wäre fatal? Dann haben Sie, um Ihr Spiel zu ändern und dies bedeutet, dass Sie nicht an diesen Punkten.
Es gibt zwei Möglichkeiten, dieses Problem zu lösen. Die erste ist die frühe Punkten zu einem späteren Zeitpunkt zu bevorzugen. In unserem Beispiel ist es besser, die erste Zeile des Spiels wählen Sie über die zweite.
Die zweite Möglichkeit ist die Verwendung Ruhesuche :
Der Horizont Effekt kann durch die Erweiterung der Such-Algorithmus mit einem Ruhesuche gemildert werden. Dies gibt dem Suchalgorithmus Fähigkeit, über seinen Horizont für eine bestimmte Klasse von Bewegungen von großer Bedeutung, um das Spiel Zustand, wie fängt aussehen.
Wir haben eine Menge Änderungen am Code. Wir werden die gedruckten Versionen tragen den Quellcode (ca. 100 Seiten) zu unserem Kollegium und versucht, Optimierungen, um den Code angewendet werden kann zu finden. Schach-Programmierung ist eines der Gebiete, in denen über-Optimierung ist nicht auf runzelte die Stirn.
So nach all der harten Arbeit, wurde das Programm arbeitet gut und es könnte eine anständige Partie Schach (genügend Zeit spielen natürlich).
Übersetzen des Quellcodes
Wir waren gerade über das Sein, wie das Projekt los war glücklich, wenn es uns treffen - das Kollegium stellen eine Beschränkung, dass alle Projekte getan werden muss, mit Hilfe von Java werden. Wir hatten in den Hafen der Antrag auf Java bald.
Umschreiben der gesamten Anwendung von Grund schien zeitraubend und demotivierend. Wir brauchten einen schnelleren Weg. Was über das Konvertieren der Quelle VB6-Quellcode in Java-Code automatisch? Natürlich für diese Arbeit hätten wir ein VB, Java Language Translator schreiben. Es schien zu schwierig in Anbetracht der schnell näher Frist für Projekteinreichung. Wir heruntergeladen einige Code-Übersetzungs-Software aus dem Internet und probierte sie aus, aber keiner von ihnen schien perfekt. Konvertieren eines komplexen VB6 UI mit einem fairen Betrag von benutzerdefinierten Animationen, Java ist fast unmöglich, selbst für eine fortgeschrittene Übersetzer.
Dann hatten wir eine Idee. Regex!
Natürlich Regular Expressions sind nicht für das Parsen von Quellcode jeder Art ideal. Wir hatten keine Zeit, so beschlossen wir, es dennoch versuchen.
Im Fall von jeder anständige Schach-Programm, gibt es zwei grundlegende Teile: eine Schach-Engine und die UI-Modul. Die Schach-Engine nicht alle komplexen Berechnungen - die Aufzeichnung der Benutzer bewegt, um herauszufinden, ob eine Bewegung gültig ist oder nicht, darüber nachzudenken den besten Zug für den Computer etc. Die UI-Modul zeigt das Schachbrett an den Benutzer und erlaubt dem Benutzer zu machen eine Bewegung mit der Maus. Nun, wie Sie vielleicht schon geschlossen haben, UI Teil ist das nicht sehr übersetzbar zwischen VB6 und Java. Wir beschlossen, die UI in Java von Grund auf neu zu entwickeln.
Das Interessante an der Schach-Engine ist, dass es viele enthält und viele Berechnungen, Bedingungen und Schleifen, die sie zu einer intelligenten Zug machen zu helfen. Vielleicht sollte ich beachten, dass ein Schach-Engine nicht so angesehen werden wie intelligent. Ein Schach-Engine knirscht Millionen Zahl sehr schnell und findet heraus, die besten bewegen Sie den Computer gegen einen menschlichen Gegner machen kann. Die Züge aussehen kann intelligent, um einen menschlichen Spieler, sondern ein Schach-Engine kann nicht als ein Beispiel für eine KI-Engine betrachtet werden. Es ist nur eine Zahlenschieber unter seiner Schichten. Jedenfalls der Punkt ist, dass wir hunderte von Seiten des Codes, der rein von Algorithmen, die den Computer im Spiel eine bessere Partie Schach Aided bestanden hatte.
Wie wir herausgefunden haben, konvertieren diese Algorithmen aus VB6 Code Java war nicht so schwer wie es schien. Wir beschäftigten die Befugnisse der Regular Expressions zu tun. Hier ist ein Blick von dem, was wir taten.
1. Ersetzt durch:
Wenn mit if (
Denn mit for (
Dann mit (
Else mit) else (
End if, Next, End Function etc mit)
True mit true
False mit falschen
Und mit & &
Oder mit | |
Mod mit%
Exit For mit break;
= In bedingten Anweisungen w erden ==
usw.
2. Hinzugefügt; (Semikolon) am Ende der Zeilen, die nicht mit einer der oben genannten Keywords haben zu starten.
3. Changed the array Referenzierung Code. in Java code. Etwas wie Board(x,y) in VB6 Code wurde board[x][y] in Java-Code.
4. Es gab einige komplexe bedingte Anweisungen in den VB-Code, dass wir dachten, wäre es unmöglich, zu konvertieren mit Java Regex. Wir mussten diese manuell zu konvertieren.
5. Umgerechnet looping Aussagen der Form
For i = 0 To NumMoves - 1 to
for(int i = 0; i < numMoves-1; i++){
6. Variablendeklarationen der Form
Dim index As Integer to
int index = 0;
Es war mehr von dieser Art.
Natürlich war es nicht alle Regex Zeug. Es ist unmöglich, es richtig zu machen mit regex allein. Das kleine Programm, das wir geschrieben, um den Code zu übersetzen las jede Zeile von VB-Code getrennt und baute es zu Java, meist mit Regex. Die gesamte Übersetzung (Regex Ersatz) wurde in mehreren Durchgängen. Wir haben nie umgesetzt einer ausgewachsenen Übersetzer oder Sprache Parser.
Selbst nach diesen ganzen Zirkus Regex die Übersetzung war nicht vollständig. Wir mussten durch Großteil des Codes lesen und ändern viele Dinge, um es korrekt funktioniert. Es gibt viele Unterschiede zwischen den Sprachen (wie Array-Indizes 0 gestartet in Java und 1 in VB6) und jene für die Pflege genommen werden. Es hat uns einen etwas Mühe, um die Angaben korrekt, aber wir endlich fertig Umwandlung des Java-Code, um mit viel weniger Aufwand als es komplett neu.
Bitte lassen Sie sich nicht in diesem Artikel machen Sie denken, dass ich mit dem Anwalt Regex für diese Art von Arbeit. Ich weiß nicht.
# 1 Mehr dazu später. Erinnere mich, wenn ich vergesse. Ich verspreche, dass dies ändern Studenten das Leben vieler. 
# 2 Eine andere gute Möglichkeit ist es, Motoren pit es wider besseres Schach.
# 3 I enthalten das Wort "AI" gibt es nur, damit ich diese Notiz zu schreiben. Schach-Algorithmen sind nicht als künstliche Intelligenz. Computer Schach ist ein Zahlenverarbeitung Problem. Die Umsetzung der Algorithmen in die effizienteste Art und Weise ist der beste Weg, um gute Ergebnisse zu erzielen. Es gibt keine Intelligenz beteiligt sind (im Vergleich zu realen KI-Techniken wie neuronale Netze).
# 4 Es ist begrenzt durch die Rechenleistung Sie haben. Im Durchschnitt der Anzahl der gültigen bewegt haben Sie für jeden Schachzug ist etwa 30. Wenn Sie im Voraus gehen bewegt zur Suche 8, müssen Sie number search bis 30 ^ 8 Knoten, die große ist ein sehr.
