geschwindigkeitsproblem, std::vector<> schuld?
-
Shade Of Mine schrieb:
hier lohnen sich uU micro optimierungen. wie zB die labels nach der wahrscheinlichkeit wie oft sie angesprungen werden ordnen. etc.
ich hab oft solche konstrukte:
switch(feld[x][y]) { case A: case B: case -A: case -B: //tu was mit feld... if(feld[x][y] == A) { //tu noch was zusätzliches } if(feld[x][y] == -B) { //tu was anderes zusätzliches } //... }also etwas gilt für mehrere werte, aber es muss mit einzelnen von den werten noch etwas anderes getan werden. dadurch verdoppeln sich quasi die abfragen
ich seh aber keine bessere möglichkeit.Shade Of Mine schrieb:
kannst ja mal die funktion posten, vielleicht faellt ja jemandem ein trick ein was man besser machen kann
die steht unter strengster geheimhaltung
ne, ich stell nachher nen teil hier rein.
Blue-Tiger schrieb:
vielleicht solltest du den Algorithmus ueberdenken, wenn sich sonst nix mehr optimieren laesst
ja da hast du wahrscheinlich recht. allerdings verwende ich schon den alpha-beta algorithmus, mitlerweile mit iterativer tiefenerhöhung und zugsortierung.
ich könnte noch weitere heuristiken einführen, die rekursionstiefe würde natürlich steigen aber damit veringere ich gleichzeitig die spielstärke. dort das passende mittelmaß zu finden ist nicht ganz so leicht.shredder schaft es auf meinem rechner spielend 9 halbzüge vorrauszudenken. mein programm braucht atm 2 minuten für 6 halbzüge, für 7 wahrscheinlich stunden.
-
borg schrieb:
dadurch verdoppeln sich quasi die abfragen
ich seh aber keine bessere möglichkeit.kannst du den gemeinsamen code denn nicht in eine funktion packen?
-
Shade Of Mine schrieb:
kannst du den gemeinsamen code denn nicht in eine funktion packen?
oh, du hast recht. das geht tatsächlich in den meisten fällen
hier mal ein paar konstrukte die oft vorkommen
int score = 0; for(size_t x = 0; x < field.size(); ++x) for(size_t y = 0; y < field[0].size(); ++y) { int s = 0; switch(field[x][y]) { case PAWN: case -PAWN: { score += field[x][y]; // mitte besetzen if((x == 3 && y == 3) || (x == 3 && y == 4) || (x == 4 && y == 3) || (x == 4 && y == 4)) s += cpBonus::PAWN_AT_MID_POS; // die bauern auf c,d,e,f if(x > 1 && x < 6) s += cpBonus::CRITICAL_PAWN; //unterstützende bauern // b b b //b oder b oder b b if(inField(x, y, x+1, y+1) && field[x+1][y+1] == field[x][y]) s += cpBonus::SUPPORT_PAWN; if(inField(x, y, x-1, y+1) && field[x-1][y+1] == field[x][y]) s += cpBonus::SUPPORT_PAWN; if(inField(x, y, x+1, y-1) && field[x+1][y-1] == field[x][y]) s += cpBonus::SUPPORT_PAWN; if(inField(x, y, x-1, y-1) && field[x-1][y-1] == field[x][y]) s += cpBonus::SUPPORT_PAWN; //bauern übereinander // b // b //---------sehr unnütz dann oder? WERT ÜBERPRÜFEN!!!!! if(inField(x, y, x, y-2) && field[x][y-2] == field[x][y]) s -= cpBonus::PAWM_ABOVE_PAWN; if(inField(x, y, x, y-1) && field[x][y-1] == field[x][y]) s -= cpBonus::PAWM_ABOVE_PAWN; if(inField(x, y, x, y+1) && field[x][y+1] == field[x][y]) s -= cpBonus::PAWM_ABOVE_PAWN; if(inField(x, y, x, y+2) && field[x][y+2] == field[x][y]) s -= cpBonus::PAWM_ABOVE_PAWN; //------SNIP------- // hier könnt ich den oberen teil in eine funktion packen und // bei PAWN funktion() oder bei -PAWN -funktion() aufrufen // :+1: if(field[x][y] == PAWN) { score += cpMatrixWhite::PAWN[x][y]; score += s; } else { score -= cpMatrixBlack::PAWN[x][y]; score -= s; } } break; case KNIGHT: case -KNIGHT: { //------SNIP------ if(field[x][y] == KNIGHT) { //springer-gabel (weiss) int count = 0; for(size_t i = 0; i < 8; ++i) count += (inField(x + drcWhite::KNIGHT[i][0], y + drcWhite::KNIGHT[i][1]) && field[x + drcWhite::KNIGHT[i][0]][y + drcWhite::KNIGHT[i][1]] < 0 && field[x + drcWhite::KNIGHT[i][0]][y + drcWhite::KNIGHT[i][1]] != -KNIGHT); if(count > 1) score += cpBonus::KNIGHT_FORK; score += cpMatrixWhite::KNIGHT[x][y]; score += s; } else { //springer-gabel (schwarz) int count = 0; for(size_t i = 0; i < 8; ++i) count += (inField(x + drcBlack::KNIGHT[i][0], y + drcBlack::KNIGHT[i][1]) && field[x + drcBlack::KNIGHT[i][0]][y + drcBlack::KNIGHT[i][1]] > 0 && field[x + drcBlack::KNIGHT[i][0]][y + drcBlack::KNIGHT[i][1]] != KNIGHT); if(count > 1) score -= cpBonus::KNIGHT_FORK; score -= cpMatrixBlack::KNIGHT[x][y]; score -= s; } } break; //--------SNIP--------mal abgesehen davon das ich gemeinsame berechnungen auslagern kann, gibt es sonst was an den konstruktionen zu verbessern? solche wie die oben kommen oft vor. also ich addiere oft boolsche werte auf, gibts da vielleicht schnellere möglichkeiten.
-
WTF ist **-**KNIGHT und **-**PAWN?!!?!?!
-
Optimizer schrieb:
WTF ist **-**KNIGHT und **-**PAWN?!!?!?!
schwarze bauern und schwarze springer. man rechnet in der schachtheorie in der einheit cp. cp = centipawn (hunderstelbauern). wenn man jetzt also das feld bewertet und man bekommt am ende -1500 cp raus, siehts sehr gut für schwarz aus. wenn schwarz am zug ist sollte diese abzweigung im baum weiter untersucht werden, vielleicht ist sie ein paar halbzüge weiter gar nicht mehr so gut, weil sich der schlagabtausch negativ für schwarz entwickelt. wenn bei einer bewertung 0 cp rauskommt, ist der stand zu dem zeitpunkt zu 100% ausgeglichen. positive werte sind gut für weiß.
ich hab die ganzen bewertungen jetzt in funktionen aufgeteilt, die neue profiler-ausgabe ist sehr interessant:Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
48.54 1.33 1.33 550960 0.00 0.00 Engine::evaluatePosition(bool)
38.69 2.39 1.06 8345513 0.00 0.00 Engine::evaluatePawn(int, int)
3.28 2.48 0.09 564928 0.00 0.00 Engine::moveBackward(int, int)
2.55 2.55 0.07 564930 0.00 0.00 Engine::moveForward(int, int)
1.46 2.59 0.04 13970 0.00 0.00 Engine::findMoveList(bool, int)
...die bauernbewertung ist mehr als 30x so resourcenhungrig wie alle anderen einzelbewertungen zusammen. das liegt einfach daran das bauern schwerer zu bewerten sind als die anderen figuren, ausserdem gibts 16 bauern, von den anderen figuren höchstens 4. vielleicht kann ich da was drehen wenn ich eine heuristik einbaue die bauern welche beim aktuellem spielstand unwichtig sind gar nicht bewertet.
ich hab jetzt die reihenfolge so gemacht das oft auftretenes am anfang abgefragt wird und neben der funktionsaufteilung noch andere kleinigkeiten geändert.
die denkzeit pro halbzug ist auf ca. 1/4 geschrumpft! also mitlerweile nur noch rund 30 sec bei 6 halbzügen.
danke erstmal an alleersteres hat übrigens am meisten gebracht.
-
borg schrieb:
if(inField(x, y, x-1, y+1) && field[x-1][y+1] == field[x][y]) s += cpBonus::SUPPORT_PAWN;ich fürchte, da geht einiges.
wie oben schon von mir vermutet, ist das problem beim op[][], der geht schneller.
die größe ist doch fest, gell? sieht so nach einem schachbrett aus.also bau auf jeden fall ein 2d-array mit festen größen als template-parameter. oder gleich ganz fest, ist ja hier egal. die größe mit der bei jedem zugriff multipliziert werden muss, soll eine zweierpotenz sein. dann haste nur noch addidionen und einema << im op[][]. das ist schonmal recht fein.
oder mach ein 1d-array! und definiere PLUSX=1, MINUSX=-1, PLUSY=8, MINUSY=-8.
for(size_t xy = 0; xy < field.size(); ++xy) ... if(/*inField(x, y, x-1, y+1)*/ && field[xy+MINUSX+PLUSY] == field[xy]) s += cpBonus::SUPPORT_PAWN;so haste immer nur eine addition im op[][].
dann zu dem inField, wo ich gar nicht so genau weiß, was das macht. stellt es nur fest, ob die koordinaten im feld sind, also noch gültig?
das kann weg. bau ein schachbrett immer mit *todesrand*. also nicht 8*8, sondern 12*12, wovon aber nur die mittleren 8*8 bespielt werden.
setz dann zum beispiel ne vierte farbe ein. also wie EMPTY=0,BLACK=1,WHITE=2,DEAD=3 und setz auf den todesrand lauter tote bauern. normalerweise sorgste ja dafür, daß dein eigener springer nicht eigene firuren schlägt mit if(me.color!=victim.color) moveTo(victim) oder so. müßte wohl zu if(!(me.color&victim.color)) moveTo(victim) werden. der todesrand hat breite von 2, damit auch jeder springer am rand immer dumm gucken kann, wo er hinhopsen mag, ohne über den rand der welt zu blicken.
-
volkard schrieb:
dann zu dem inField, wo ich gar nicht so genau weiß, was das macht. stellt es nur fest, ob die koordinaten im feld sind, also noch gültig?
das kann weg. bau ein schachbrett immer mit *todesrand*. also nicht 8*8, sondern 12*12, wovon aber nur die mittleren 8*8 bespielt werden.
setz dann zum beispiel ne vierte farbe ein. also wie EMPTY=0,BLACK=1,WHITE=2,DEAD=3 und setz auf den todesrand lauter tote bauern. normalerweise sorgste ja dafür, daß dein eigener springer nicht eigene firuren schlägt mit if(me.color!=victim.color) moveTo(victim) oder so. müßte wohl zu if(!(me.color&victim.color)) moveTo(victim) werden. der todesrand hat breite von 2, damit auch jeder springer am rand immer dumm gucken kann, wo er hinhopsen mag, ohne über den rand der welt zu blicken.ja, es gibt einige schach-engines mit "todesrand", das ist aber nur auf den ersten blick toll. ein feld hat 3 zustände, es ist leer (0) es steht eine weiße figur drauf (positiv) oder er steht eine schwarze figur drauf (negativ). so ein rand führt dadurch zu einer unmenge von abfragen und komplikationen an allen möglichen stellen. das ist dann zwar insgesammt immernoch schneller, es kommt aber zu undurchsichtigen rechnungen und horror-if-abfragen. die inField funktion beansprucht nichtmal 1% der rechenzeit. die bleibt.
(ich kenne den code von einer menge schach-maschinen, jene die eine beachtliche stärke erreicht haben können nicht mehr weiterentwickelt werden weil niemand mehr etwas ändern kann ohne das an einer anderen stelle bugs auftreten. [siehe gnu chess]).die vectoren werd ich dann wohl doch mal testhalber austauschen, ich poste es hier wenn ich eine schöne 1d-lösung gefunden hab wodurch es nicht zu unleserlich wird.
-
borg schrieb:
ja, es gibt einige schach-engines mit "todesrand", das ist aber nur auf den ersten blick toll...das ist dann zwar insgesammt immernoch schneller, es kommt aber zu undurchsichtigen rechnungen und horror-if-abfragen.
uih. und ich dachte immer, de rtodesrand macht die sache echt einfacher. ok, wieder was gelernt.
finde ich fein, daß du lesbarkeit wichtiger nimmst als das letzte fitzelchen speed. das wird sich auszahlen in mehr speed im endeffekt.
[/quote]die vectoren werd ich dann wohl doch mal testhalber austauschen, ich poste es hier wenn ich eine schöne 1d-lösung gefunden hab wodurch es nicht zu unleserlich wird.[/quote]
ok. den versuch ist es wert. bin gespannt, ob es lesbar wird.
-
Mach doch eine Liste von Figuren und merk Dir deren Position, anstatt ein Schachbrett als Array zu verwenden. Dadurch kann man sehr viel Zeit sparen. std::deque als doppelt verkettete Liste geht auch schneller zu durchlaufen als ein std::vector.
Oder besser noch: Mach beides. Das Schachbrett benutzt Du nur, um benachbarte Figuren rauszufinden. Die Figuren selbst stehen in einer Liste.
Indem Du mit Objekten arbeitest, kannst Du Fallunterscheidungen vollstaendig eliminieren.
class Figur; class Schachbrett { public: // white-boxing: ermoeglicht Direktzugriff auf Elemente Figur* brett[8][8]; }; enum FigurTyp { Leer, Bauer, ... }; enum Farbe { Keine, Weiss, Schwarz }; class Figur { public: FigurTyp typ; Farbe farbe; int x; int y; Figur( FigurTyp _typ, Farbe _farbe ); virtual ~Figur( void ); virtual void evaluatePosition( void ); }; class Bauer : public Figur { public: Bauer( Farbe _farbe ); virtual ~Bauer( void ); virtual void evaluatePosition( void ); }; // ... typedef std::deque<Figur*> FigurListe; typedef FigurListe::const_iterator FigurCIter; class Schachspiel { public: Schachbrett sb; FigurListe fl; void figurHinzu( Figur* figur, int x, int y ); void figurEntf( Figur* figur ); void evaluatePosition( void ); }; void figurHinzu( Figur* figur, int x, int y ) { figur->x = x&7; figur->y = y&7; sb.brett[figur->x][figur->y] = figur; fl.push_back( figur ); } void figurEntf( Figur* figur ) { sb.brett[figur->x][figur->y] = 0; fl.remove( figur ); } void evaluatePosition( void ) { FigurCIter iter = fl.begin(); while ( iter != fl.end() ) { Figur* fig = *iter++; // iter muss inkrementiert werden, falls // Figur vom Brett entfernt wird. fig->evaluatePosition(); } } // etc...Hoffe, das hilft!
-
so eine oop variante ist eine überlegung wert. im momment speichere ich die figur auf ein array, das hat den vorteil das ich die figur darauf schnell hin und herschieben kann.
wenn ich eine liste von figuren anlege und die figur selbst wissen lasse wo sie steht, kann ich die liste schneller durchgehen, wahrscheinlich würde der zugriff auf eine bestimmte figur an stelle xy aber nicht mehr so schnell gehen. ich müsste zu jeder figur ein bitboard, also einfach ein 64bit datentyp, anlegen und dort eine 1 eintragen wo sie hinspringen kann. damit würde die überprüfung ob sich eine figur noch im spielfeld befindet flachfallen, weil ich bei jeder bewegung einfach automatisch alle bitboards anpasse.
im endeffekt würden fast alle funktionen schneller werden, nur die evaluation wird wahrscheinlich durch die kapselung langsamer. dummerweise ist das aber jetzt schon der flaschenhals
ich werds heute nacht mal ausprobieren. hab im momment massig zeit :p .edit: die oop variante ist leider unpraktikabel. die doppelte speicherung saugt an der performance und ich bekomme probleme bei der zugsortierung, da müsste ich einen riesen aufwand betreiben.
der ansatz ist aber bestimmt schön wenn man eine schach-gui machen möchteein einfaches array in dem man rumwuselt ist wahrscheinlich doch die einzige möglichkeit eine hohe rekursionstiefe zu erlangen.
-
hola borg...
http://www.c-plusplus.net/forum/viewtopic-var-t-is-102404.html
da gehts unter anderem um ne sogenannte webdesigneroptimierung (volkards namensgebung). vielleicht hilft die ja bei dir auch.
Meep Meep
-
Kleinigkeiten kann man viele finden.
. if((x == 3 && y == 3) || (x == 3 && y == 4) || (x == 4 && y == 3) || (x == 4 && y == 4))könnte man das nicht einfach als
. if((x == 3 || x == 4) && (y == 3 || y == 4))schreiben?
...
-
Helium schrieb:
Kleinigkeiten kann man viele finden.
. if((x == 3 && y == 3) || (x == 3 && y == 4) || (x == 4 && y == 3) || (x == 4 && y == 4))könnte man das nicht einfach als
. if((x == 3 || x == 4) && (y == 3 || y == 4))schreiben?
...oh, da hast du wohl recht.
wobei ich annehme das der compiler solche ausdrücke in konjunktive normalform bringt.
-
borg schrieb:
wobei ich annehme das der compiler solche ausdrücke in konjunktive normalform bringt.
Das glaube ich nicht. Warum sollte er auch.
Zudem würde er sich damit die Auswertung ja viel schwerer machen. Er muß ja bei && (||) aufhören, sobald der erste operand falsch (wahr) ist.
-
borg schrieb:
wobei ich annehme das der compiler solche ausdrücke in konjunktive normalform bringt.
ganz bestimmt nicht. ok, er dürfte das zwar, aber was ist, wenn ich aus der datenlage her genau weiß, daß die bedingung zu 99.9% aller fälle bei (x == 3 && y == 3) bereits abbricht? ich hab mit absicht diese umformung gemacht und der compiler hackt es mir wieder kaputt?
-
Kann das nicht auch die Semantik verändern, wie Jester evtl. andeuten wollte? Die Ausdrücke können ja vor allem auch Seiteneffekte haben, solche Umformungen könnten doch die Auswertungsreihenfolge ändern, oder?
-
das ist zwar ein bisschen OT aber in diesem thread ist wenigstens schon bekannt worum es geht.
ich brauch ein hashwert von dem schachbrett. im momment mach ich es sehr naiv:
int hash = 0; for(size_t x = 0; x < BOARD_LENGTH; ++x) for(size_t y = 0; y < BOARD_LENGTH; ++y) hash+=(x*y+y)*field[x][y]; return hash;in field stehen die unterschiedlichen werte der figuren. nachdem das ganze dann 50x übergelaufen ist(
) stehen in hash immer werte zwischen -40000 und -60000. und es kommt viiiiiel zu oft zu kollisionen. hat irgendwer eine idee wie ich ohne großen rechenaufwand an einen akzeptablen hashwert komme? (akzeptabel = in weniger als 0,1% der fälle eine kollision, bei 100 hashwerten)
besonders sehr ähnliche felder sollten natürlich unterschiedliche hashwerte haben.ich brauche das um stellungswiederholungen zu bemerken, ich hab zuerst einfach bei jeder stellung das ganze feld gespeichert, alllerdings war der aufwand beim vergleichen der felder inakzeptabel.
ps: ihr habt natürlich recht mit dem vereinfachen der ausdrücke
.
pps: das umstellen auf 1d-arrays hat keinen messbaren unterschied gebracht.
-
borg schrieb:
ich brauch ein hashwert von dem schachbrett. im momment mach ich es sehr naiv:
int hash = 0; for(size_t x = 0; x < BOARD_LENGTH; ++x) for(size_t y = 0; y < BOARD_LENGTH; ++y) hash+=(x*y+y)*field[x][y]; return hash;in field[x][y] stehen zahlen von 0 bis 15?
als verbietet sichhash+=field[x][y];aber das weißte ja schon selber. es würde nur das material zählen und gegen züge ohne schlagen resistenz sein.
das (x*y+y) ist teuer. eine plutimikation hat viele takte.
mir drängt sich soforthash=hash*31+field[x][y];auf.
31 kann der compiler extrem schnell. hash muss vom typ unsigned int sein.
beim haschen von strings ist hash=hash31+str[i]; extrem beliebt.
der plutimikator muss ungerade sein, weil sonst alle alten bits nur herausgeschubst werden.nun zu deinem
hash+=(x*y+y)*field[x][y];wir erkennen: wenn y gerade ist, dann ist (x*y+y) durch 4 teilbar. wenn field[x][y] wie ich annahm nur werte zwischen 0 und 15 haben kann, verfummelst du damit nur die bits 2 bis 17.
wenn y gerade ist, verfummelst du nur diewerte 0 bis 15.
also zusammen nur 0 bis 17. ist also nur 0 bis 131072.
deckt sich mit deine angaben. offensichtlich nimmst du signed und -7 bis 7 als figuren.
probier mal meinen hasher (und bleib bei signed).
alsohash=hash<<5-hash+field[x][y];und poste natürlich, ob es was bringt.
ich habe das gefühl, daß mein hasher alle bits recht gut belegt. aber sicher ist man hei hash-funktionen nie. man kann da nur ausprobieren und messen.
-
volkard schrieb:
in field[x][y] stehen zahlen von 0 bis 15?
nein, es steht dort oft 0, oft 100 und -100, und manchmal 301, 302, 500, 900, 10000 + die negationen. also die figurenwerte in centipawn(hunderstelbauern).
wenn ich die figuren durchnumeriere und reinschreibe brauch ich bei der figurenbewertung die doppelte anzahl an arrayzugriffen.volkard schrieb:
probier mal meinen hasher (und bleib bei signed).
alsohash=hash<<5-hash+field[x][y];ok probier ich mal. wenns gut verteilt aber es trotzdem zuviele kollisionen gibt kann ich natürlich auch ein 64bit-datentyp nehmen, damit muss es dann aber gehen.
-
habs als erstes damit probiert:
hash=hash*31+field[x][y];hab nen paar spiele durchrechnen lassen und es gab keine kollisionen.
die zahlen sehen so aus:logfile schrieb:
uci
uciok
isready
readyok
position startpos moves g1f3 b8c6 d2d4 d7d5 c1f4 g8f6 b1c3 e7e6 c3b5 f8d6 f4d6 c
7d6 e2e3 e8g8 c2c4 d8b6 c4d5 b6a5 d1d2 a5d2 f3d2 c6b4 a2a3 b4c2 e1e2 c2a1 d2f3 a
7a6 b5d6 f6g4 d5e6 f7e6 h2h3 g4f6 e3e4 f8d8 e4e5 f6d5 e2d2 a1b3 d2c2 b3a1 c2b1 a
1b3 b1c2 b3a5 f3g5 b7b5 g5f7 d8d7 f7g5 b5b4 a3b4 d5b4 c2b1 a8b8 d6c8 d7d4 f1a6 b
4d3 a6d3 d4d3 c8d6 b8b6 f2f4 d3d2 h1g1 b6b2
-1234213860
-1215141476
-524258660
1484196252
890199830
2127233174
-608284906
821574606
2071283278
1716901774
1882200763
976518534
1387875902
-1266444738
932749118
754251838
-1752365038
-414537574
1231886626
536449558
885021110
213097270
-788034578
-701771410
-1099217522
1755727262
-79380862
-2132948166
-340472774
740454842
-1966767258
-1939029830
-1927136910
1286902770
745983034
-287230918
-581774606
1505600654
1248433294
-1804810738
-769083890
-2010807154
-290168722
951554542
-769083890
-2044843122
-403891698
1704309006
907893646
-1653767946
-857352586
-1969959634
-133439526
1416995674
-1157333190
124078906
-252157721
1101772571
547124537
-328919083
-2076556435
1686588898
-750335902
5338466
-256803230
1881700858
490876410
726694550woran erkenne ich ob die gut verteilt sind?
ich teste mal noch deinen anderen vorschlag.