Effiziente Programme Aufgabe 2021w

Sie können sich eine beliebige Aufgabe suchen. Wenn Sie das nicht wollen, ist die vorgegebene Aufgabe dieses Jahr, eine Implementation einer Variant des Spiels Fünf in eine Reihe: Das Spielfeld ist unbegrenzt groß, aber ein Stein darf nur in den 24 Feldern gesetzt werden, die von einem schon gesetzten Stein maximal 2 Felder entfernt sind (horizontal, vertikal, und/oder diagonal).

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 movex movey infile outfile

movex und movey sind die Koordinaten, auf die der Stein gesetzt werden soll.

infile ist der Name einer Datei, die den Spielstand vor dem Zug enthält.

outfile ist der Name einer Datei, die den Spielstand nach dem Zug enthält. Die beiden Dateinamen dürfen gleich sein.

Ob x oder o gesetzt wird, hängt vom aktuellen Zustand ab (x beginnt).

turn gibt entweder aus, dass der Zug zum Sieg geführt hat, oder es gibt den neuen Spielstand in folgender Form aus:

Beispiel: Der Aufruf 

turn 1 1 start1 p2
erzeugt die folgende Ausgabe: 
Old position:
   0 1 2 3 4
 4           4
 3           3
 2     x     2
 1           1
 0           0
   0 1 2 3 4
o to move

New position:
   0 1 2 3 4 5
 5             5
 4             4
 3       x     3
 2     o       2
 1             1
 0             0
   0 1 2 3 4 5
x to move
Die Spalten und Zeilen 0 und 1 bleiben in dieser Darstellung immer frei; wenn ein Stein dorthin gesetzt wird, wird das Koordinatensystem entsprechend verschoben, damit sie wieder frei sind (diese Koordinaten sind also nur dazu da, damit man Steine dorthin setzen kann).

Computerzüge

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

comp depth infile

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

comp 4 start1
vom Computer einen Zug für die eine Start-Spielsituation empfehlen lassen. Die Ausgabe fuer diesen Aufruf ist: 
Position:
   0 1 2 3 4
 4           4
 3           3
 2     x     2
 1           1
 0           0
   0 1 2 3 4

Best move: 1 1 Value: 42
Wobei Value die Bewertung dieses Zugs ist (das sagt einem wenig).

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 4 start1
Position:
   0 1 2 3 4
 4           4
 3           3
 2     x     2
 1           1
 0           0
   0 1 2 3 4

Best move: 1 1 Value: 42

 Performance counter stats for 'comp 4 start1':

   553,019,320,802      cycles:u
 1,023,958,490,477      instructions:u            #    1.85  insn per cycle
   181,864,081,572      branches:u
     5,962,254,695      branch-misses:u           #    3.28% of all branches

     171.738088549 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 100 Milliarden Zyklen 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 3 und braucht dafür 15,48Gcycles bzw. 2.81s.

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 Spiel allgemein schnell ist, nicht nur für diese Stellung.

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 fuenf.zip bzw. Sie können ihn auf der g0 von /nfs/unsafe/httpd/ftp/pub/anton/lvas/effizienz-aufgabe21 kopieren.
[ICO]NameLast modifiedSizeDescription
[DIR]Parent Directory  -  
[ ]Makefile14-Dec-2021 15:25 1.1K 
[TXT]common.c13-Dec-2021 19:38 5.4K 
[TXT]common.h13-Dec-2021 12:12 343  
[TXT]comp.c14-Dec-2021 15:17 6.0K 
[ ]start113-Dec-2021 11:38 2  
[TXT]turn.c13-Dec-2021 09:33 1.0K 

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