# Effiziente Programme - WS19 * Manuel Kroiß (01526926) * Stefan Grossauer (01525664) * Matthias Streimetweger (01527130) ## Aufgabe: Oware [Link zur Angabe](http://www.complang.tuwien.ac.at/anton/lvas/effizienz-aufgabe19/) ## Ausgangssituation auf der G0 ``` 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,139,913,295 cycles:u 711,065,944,797 instructions:u # 2.07 insn per cycle 123,045,592,316 branches:u 4,635,686,521 branch-misses:u # 3.77% of all branches 104.887598993 seconds time elapsed ``` ## Verbesserung 1: Negamax -> Alpha-Beta Suche Als ersten Schritt haben wir den Negamax Algorithmus verbessert und die Implementierung auf einer Alpha-Beta Suche geändert. Die Verbesserung liegt darin, dass hier obere und untere Grenzen für den maximierenden und minimierenden Spieler berechnet werden. Diese Grenzen werden vor dem Verzweigen in einen Subbaum überprüft. Ist das Ergebnis (z.B. beim minimierenden Spieler) bereits besser als das beste bisher gefundene Ergebnis, kann die Suche abgebrochen werden. Der maxmimierende Spieler würde diesen Pfad nicht wählen, da es einen Vorteil für den Gegner bringen würde. Diese Änderung brachte folgendes Ergebnis auf der G0: ``` 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': 417,501,939 cycles:u 822,622,869 instructions:u # 1.97 insn per cycle 134,310,883 branches:u 6,200,074 branch-misses:u # 4.62% of all branches 0.170344954 seconds time elapsed ``` Mit dieser Verbesserung kann auf der G0 in <10s eine Tiefe von 16 berechnet werden. Ergebnis: ``` Position: 4 0 0 0 1 0 0 0 0 14 9 8 7 5 Best move (1-6): 6 Value: -2 Performance counter stats for 'comp 16 0 14 9 8 7 5 0 0 1 0 0 0 4 0': 25,138,956,223 cycles:u 49,021,709,951 instructions:u # 1.95 insn per cycle 7,934,781,444 branches:u 383,727,474 branch-misses:u # 4.84% of all branches 7.525238739 seconds time elapsed ``` ## Verbesserung 2: Optimierung Alpha-Beta Suche: Zugsortierung Die Alpha-Beta Suche funktioniert deshalb so gut, weil nur jene Teilbäume weiter betrachtet werden, wo nicht bereits klar ist dass diese zu keinem besseren Ergebnis mehr führen können. Teilbäume mit 100% nicht zielführendem Ergebnis werden weggelassen (pruning). Um dies zu Verstärken, kann man die Züge vorsortieren. Die Idee ist, dass am Anfang Züge berechnet werden, welche wahrscheinlich zu einem bereits sehr guten Ergebnis führen. Ist dieses sehr gute Ergebnis bekannt, können bei der anschließenden Berechnung der Teilbäume bereits sehr viele Teilbäume ausgelassen werden. Für die Vorsortierung gibt es verschiedene Heuristiken. Wir haben uns für die Heuristik * H2 ordering for the houses with the minimum amount of pieces in a house entschieden. [1] Wir haben also die Züge so sortiert, dass als erstes die Felder mit der minimalen Anzahl an Kugeln in einem Haus für die Berechnung des Suchbaums verwendet werden. Man sieht, dass der gewählte Zug hier abweicht. Dies ist aber auf Grund der Umsortierung. Der Value des gewählten Zuges bleibt nämlich gleich (d.h. Zug 5 und 6 sind gleich gut). Weitere Optimierungen wären hier möglich, in dem man alle von Prof. Pier Luca Lanzi [1] erwähnten Heuristiken kombiniert und gewichtet. [1] Prof. Pier Luca Lanzi. Design of Artificial Intelligence for Mancala Games. 2015-2016 Das Ergebnis dieser Verbesserung auf der G0 lautet: ``` Position: 4 0 0 0 1 0 0 0 0 14 9 8 7 5 Best move (1-6): 6 Value: -1 Performance counter stats for 'comp 12 0 14 9 8 7 5 0 0 1 0 0 0 4 0': 394,428,310 cycles:u 704,665,797 instructions:u # 1.79 insn per cycle 96,352,514 branches:u 3,779,656 branch-misses:u # 3.92% of all branches 0.181917691 seconds time elapsed ``` Mit dieser Verbesserung schaffen wir eine Tiefe von 17 innerhalb von 10s auf der G0. Ergebnis: ``` Position: 4 0 0 0 1 0 0 0 0 14 9 8 7 5 Best move (1-6): 6 Value: -4 Performance counter stats for 'comp 17 0 14 9 8 7 5 0 0 1 0 0 0 4 0': 14,975,612,589 cycles:u 26,343,514,513 instructions:u # 1.76 insn per cycle 3,648,942,328 branches:u 158,571,531 branch-misses:u # 4.35% of all branches 4.511001921 seconds time elapsed ``` ## Verbesserung 3: Low-Level-Optimierungen In den Abschnitten 3a-3e werden diverse Low-Level-Optimierungen genauer beschrieben. ### 3a: Array kopieren durch memcpy ersetzen In jeder Schleifeniteration in der Funktion bestmove(...) werden zwei Arrays kopiert. Dies wird mit Hilfe einer Schleife umgesetzt, welche über die Array-Elemente iteriert. Eine schnellere Möglichkeit, Arrays (die immer dieselbe Größe haben) zu kopieren, ist stattdessen memcpy(...) zu verwenden. Dadurch wird die Schleife nicht mehr benötigt. ``` /* alter Code for (int j = 0; j <= houses; j++) { ts1[j] = thisside[j]; os1[j] = otherside[j]; } */ // neuer Code memcpy(ts1, thisside, sizeof(int) * (houses + 1)); memcpy(os1, otherside, sizeof(int) * (houses + 1)); ``` Das Ergebnis dieser Verbesserung auf der G0 lautet: ``` Position: 4 0 0 0 1 0 0 0 0 14 9 8 7 5 Best move (1-6): 6 Value: -1 Performance counter stats for './optcomp 12 0 14 9 8 7 5 0 0 1 0 0 0 4 0': 380,390,482 cycles:u 678,832,016 instructions:u # 1.78 insn per cycle 96,352,518 branches:u 3,852,865 branch-misses:u # 4.00% of all branches 0.160595215 seconds time elapsed ``` ### 3b: Test Reordering Hier wird die Reihenfolge der aufeinander folgenden Überprüfungen der value1(...) Funktion vertauscht. Es ist zu erwarten, dass es wesentlich mehr Züge gibt, welche nicht zum Sieg führen. Wird also zuerst überprüft, ob kein Sieg vorliegt, muss die zweite Überprüfung nur noch in Situationen mit einem Sieg oder Unentschieden überprüft werden. In den restlichen Situationen muss nur noch eine Überprüfung ausegführt werden. Das Ergebnis dieser Verbesserung auf der G0 lautet: ``` Position: 4 0 0 0 1 0 0 0 0 14 9 8 7 5 Best move (1-6): 6 Value: -1 Performance counter stats for './optcomp 12 0 14 9 8 7 5 0 0 1 0 0 0 4 0': 369,129,156 cycles:u 670,102,620 instructions:u # 1.82 insn per cycle 99,262,314 branches:u 3,853,836 branch-misses:u # 3.88% of all branches 0.158572777 seconds time elapsed ``` ### 3c: Boolean/State Variable Elimination Hier wurde die Variable v in der value1(...) Funktion eliminiert, indem direkt der Wert anstatt dem Array an die Funktion übergeben wird. Die Variable wird dabei jedoch nicht ganz eliminiert, da sie immer noch als Funktionsparameter existiert. Das Ergebnis dieser Verbesserung auf der G0 lautet: ``` Position: 4 0 0 0 1 0 0 0 0 14 9 8 7 5 Best move (1-6): 6 Value: -1 Performance counter stats for './optcomp 12 0 14 9 8 7 5 0 0 1 0 0 0 4 0': 369,277,957 cycles:u 670,102,620 instructions:u # 1.81 insn per cycle 99,262,314 branches:u 3,854,120 branch-misses:u # 3.88% of all branches 0.158675513 seconds time elapsed ``` ### 3d: Unnötigen Jump entfernen In unserer Implementierung der Alpha-Beta-Suche gab es einen break-Befehl, der die Schleife abbricht und anschließend wird der Wert best zurückgeliefert. Wenn direkt best zurückgeliefert wird anstatt einem break, kann ein Jump zum Ende der Schleife eingespart werden. Das Ergebnis dieser Verbesserung auf der G0 lautet: ``` Position: 4 0 0 0 1 0 0 0 0 14 9 8 7 5 Best move (1-6): 6 Value: -1 Performance counter stats for './optcomp 12 0 14 9 8 7 5 0 0 1 0 0 0 4 0': 369,251,442 cycles:u 670,102,619 instructions:u # 1.81 insn per cycle 99,262,313 branches:u 3,855,578 branch-misses:u # 3.88% of all branches 0.151860933 seconds time elapsed ``` ### 3e: gcc -O3 Die gcc-Option -O3 hat keine weiteren Verbesserungen mehr gebracht. Die Resultate waren dieselben wie bei 3d. ### maximale Tiefe in <10s Mit den 4 genannten Low-Level-Optimierungen (3a-3d) schaffen wir (wie auch zuvor) eine Tiefe von 17 innerhalb von 10s auf der G0. Die Anzahl der Cycles und die Laufzeit sind jedoch geringer als zuvor. Es ist beinahe eine Tiefe von 18 möglich (13.93 seconds). Ergebnis: ``` Position: 4 0 0 0 1 0 0 0 0 14 9 8 7 5 Best move (1-6): 6 Value: -4 Performance counter stats for './comp 17 0 14 9 8 7 5 0 0 1 0 0 0 4 0': 14,041,591,894 cycles:u 25,049,791,313 instructions:u # 1.78 insn per cycle 3,758,594,551 branches:u 160,659,550 branch-misses:u # 4.27% of all branches 4.205388766 seconds time elapsed ``` ## Aufruf der Versionen ``` make bench # neueste Version make origbench # originale Version make alphabetabench # Alpha-Beta-Suche make sorthousesbench # Zugsortierung make optbench # Low-Level-Optimierungen make optbench3 # Low-Level-Optimierungen & -O3 ``` ## Dateien der Versionen Alle Versionen benötigen die Dateien `oware.c`, `oware.h` und `turn.c`. Zusätzlich werden folgende Dateien benötigt: ``` comp.c # neueste Version origcomp.c # originale Version alphabetacomp.c # Alpha-Beta-Suche sorthousescomp.c # Zugsortierung optcomp.c # Low-Level-Optimierungen ``` ## Zusammenfassung / Verbesserungen Folgende Verbesserungen wurden durch die einzelnen Optimierungen erzielt: | | Cycles:u | Verbesserung | | Laufzeit (s) | Verbesserung | |-------------------------|-----------------|-------------:|---|---------------|-------------:| | Originale Version | 344,139,913,295 | | | 104.887598993 | | | Alpha-Beta-Suche | 417,501,939 | 823.28% | | 0.170344954 | 614.73% | | Zugsortierung | 394,428,310 | 5.85% | | 0.181917691 | -6.36% | | Low-Level-Optimierungen | 369,251,442 | 6.82% | | 0.151860933 | 19.79% |