Effiziente Programme Aufgabe 2019w

Sie koennen sich eine beliebige Aufgabe suchen. Wenn Sie das nicht wollen, ist die vorgegebene Aufgabe dieses Jahr, eine Implementation des Spiels Oware (in der implementierten Variante ist es zulässig, einen Zug zu machen, der die verbleibenden Steine des Gegners fangen würde, aber in diesem Fall unterbleibt das Fangen).

Spielen

Der vorgegebene Code baut zwei ausführbare Dateien, turn und comp.

turn führt einen (Halb-)Zug durch, und stellt fest, ob der Zug das Spiel beendet. Es wird wie folgt aufgerufen:

turn move a1 a2 a3 a4 a5 a6 ascore b1 b2 b3 b4 b5 b6 bscore

move kann 1-6 sein, und gibt an, aus welcher Mulde (a1...a6) der Spieler die Steine nimmt. a1 a2 a3 a4 a5 a6 sind die Mulden des Spielers, der am Zug ist, b1 b2 b3 b4 b5 b6 die seines Gegners. ascore gibt an, wieviel der Spieler am Zug insgesamt gefangen hat, bscore, wieviel sein Gegner gefangen hat. turn gibt den alten und neuen Spielstand in folgender Form aus:

    b6 b5 b4 b3 b2 b1
bscore             ascore
    a1 a2 a3 a4 a5 a6
Weiters gibt es den Spielstand in der Form aus, die für den nächsten Aufruf von turn sinnvoll ist (also mit vertauschten Seiten). Beispiel: Der Aufruf 
turn 4 1 15 10 9 7 0 0 1 2 1 1 1 0 0
produziert folgende Ausgabe: 
Old position:
    0  1  1  1  2  1
  0                  0
    1 15 10  9  7  0
New position:
    1  2  2  2  3  2
  0                  0
    2 15 10  0  8  1
input for opponent move:
2 3 2 2 2 1 0 2 15 10 0 8 1 0
Jetzt kann man die letzte Zeile als Teil der Eingabe für den nächsten Zug verwenden. Wenn der andere Spieler zum Beispiel aus seiner 5. Mulde nehmen, will, kann er schreiben: 
turn 5 2 3 2 2 2 1 0 2 15 10 0 8 1 0
Wobei der Teil hinter turn 5 die letzte Zeile der Ausgabe des vorigen Zugs ist.

Computerzüge

Die ausführbare Datei comp schlägt einen Zug vor. Rufen Sie sie wie folgt auf:

comp depth a1 a2 a3 a4 a5 a6 ascore b1 b2 b3 b4 b5 b6 bscore

wobei depth die Suchtiefe angibt, und der Rest den aktuellen Spielstand, wie bei turn. Man kann sich zum Beispiel mit

comp 10 2 3 2 2 2 1 0 2 15 10 0 8 1 0
vom Computer einen Zug für die zweite Spielsituation oben empfehlen lassen.

Aufgabe

Zu optimieren ist das Programm comp. make bench ruft das Programm mit einer bestimmten Eingabe auf. Die Originalversion produziert auf der g0 folgendes Resultat: 
LC_NUMERIC=en_US.utf8 perf stat -B -e cycles:u -e instructions:u -e branches:u -e branch-misses:u comp 12 0 14 9 8 7 5 0 0 1 0 0 0 4 0
Position:
    4  0  0  0  1  0
  0                  0
    0 14  9  8  7  5
Best move (1-6): 5  Value: -1

 Performance counter stats for 'comp 12 0 14 9 8 7 5 0 0 1 0 0 0 4 0':

   344,306,194,571      cycles:u
   711,065,944,240      instructions:u            #    2.07  insn per cycle
   123,045,591,793      branches:u
     4,643,565,058      branch-misses:u           #    3.77% of all branches

     102.935136358 seconds time elapsed
Vergleichen Sie ihre optimierte Version mit der Originalversion auf dieser Eingabe bezüglich cycles:u (also Laufzeit im User-mode).

Wenn Sie gut optimieren, kann Ihr Programm deutlich tiefere Suchbäume in vertretbarer Zeit absuchen. Sie können daher auch noch angeben welche Tiefe Ihr Programm für die obige Stellung erreicht, ohne eine Laufzeit von 10s zu überschreiten, und wie lange die Suche dabei braucht (wobei das mit dem Original nur vergleichbar ist, wenn Sie dabei immer das gleiche Ergebnis liefern wie das Original mit dieser Tiefe liefern würde). Das Original erreicht Tiefe 10 und braucht dafür 13.6Gcycles bzw. 4.94s.

Es ist natürlich leicht, eine Version zu machen, die genau für diese Eingabe schnell ist (und für alle anderen so langsam wie vorher), aber damit würden Sie das Lehrziel verfehlen. Es geht also darum, eine Version zu produzieren, die beim Oware-Spiel allgemein schnell ist, nicht nur für diese Stellung. Dabei können Sie sich auf die Einschränkungen des Spiels (z.B. nur 48 Steine im Spiel) durchaus verlassen und für Ihre Optimierung ausnutzen.

Tipps

Die aktuelle Implementierung verwendet die Negamax-Variante des Minimax-Algorithmus. Klassische Verbesserungen sind die Alpha-Beta-Suche und Transpositionstabellen. Zusätzlich zu diesen algorithmischen Verbesserungen sollten Sie dem Programm auch low-level-Optimierungen angedeihen lassen, auch wenn die "nur" einen konstanten Faktor bringen.

Beschränken Sie den Speicherplatzverbrauch des Programms auf 5GB (relevant, wenn Sie Transpositionstabellen verwenden), damit mehrere Gruppen gleichzeitig auf der g0 arbeiten können.

Das eigentliche Ziel ist ja ein starker Computerspieler, der möglichst wenig Rechenzeit braucht. Es gibt eine Reihe bekannter Techniken (z.B. Ruhesuche), die die Spielstärke erhöhen sollten, aber wo das Ergebnis dann nicht direkt mit einer bestimmten Minimax-Tiefe vergleichbar ist (es können andere Zugempfehlungen herauskommen). Man müsste dann irgendwie die Spielstärke vergleichen, was sehr aufwändig ist. Aber wenn Sie in diese Richtung arbeiten wollen, lassen Sie sich nicht davon abhalten. Überlegen Sie sich, wie Sie zeigen können, dass Ihr Programm in weniger Zeit genauso viel leistet, oder in der gleichen Zeit mehr; idealerweise sollten Sie diese Argumente quantitativ untermauern können.

Code

Der Code findet sich in oware.zip bzw. Sie können ihn auf der g0 von /nfs/unsafe/httpd/ftp/pub/anton/lvas/effizienz-aufgabe19 kopieren.
[ICO]NameLast modifiedSizeDescription
[DIR]Parent Directory  -  
[ ]Makefile14-Dec-2019 17:11 1.1K 
[TXT]comp.c14-Dec-2019 14:45 1.8K 
[TXT]oware.c13-Dec-2019 19:58 3.3K 
[TXT]oware.h12-Dec-2019 15:48 329  
[ ]oware.zip14-Dec-2019 19:51 6.6K 
[TXT]turn.c13-Dec-2019 19:39 1.3K 

Apache/2.2.22 (Debian) DAV/2 mod_fcgid/2.3.6 PHP/5.4.36-0+deb7u3 mod_python/3.3.1 Python/2.7.3 mod_ssl/2.2.22 OpenSSL/1.0.1e mod_perl/2.0.7 Perl/v5.14.2 Server at www.complang.tuwien.ac.at Port 80