geschwindigkeitsproblem, std::vector<> schuld?
-
gprof hat mir folgende ausgabe geliefert:
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
12.60 7.39 7.39 951755 0.00 0.00 Engine::evaluatePosition(bool)
11.96 14.40 7.01 581049602 0.00 0.00 __gnu_cxx::__normal_iterator<std::vector<int, std::allocator<int> >, std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > >::operator+(int const&) const
9.57 20.01 5.61 581049602 0.00 0.00 std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >::operator[](unsigned)
9.13 25.36 5.35 510862274 0.00 0.00 __gnu_cxx::__normal_iterator<int, std::vector<int, std::allocator<int> > >::operator+(int const&) const
8.32 30.24 4.88 510862274 0.00 0.00 std::vector<int, std::allocator<int> >::operator[](unsigned)
8.29 35.10 4.86 1162099204 0.00 0.00 __gnu_cxx::__normal_iterator<std::vector<int, std::allocator<int> >, std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > >::__normal_iterator(std::vector<int, std::allocator<int> > const&)
7.20 39.32 4.22 1021724548 0.00 0.00 __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >::__normal_iterator(int* const&)
5.30 42.43 3.11 581049602 0.00 0.00 std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >::begin()
5.03 45.38 2.95 510862274 0.00 0.00 std::vector<int, std::allocator<int> >::begin()
2.94 47.10 1.73 118206900 0.00 0.00 Engine::inField(int, int, int, int)
2.90 48.81 1.70 581049602 0.00 0.00 __gnu_cxx::__normal_iterator<std::vector<int, std::allocator<int> >, std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > >::operator() const
2.66 50.37 1.56 510862274 0.00 0.00 __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >::operator*() const
1.35 51.16 0.79 53137621 0.00 0.00 __gnu_cxx::__normal_iterator<std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >, std::vector<std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >, std::allocator<std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > > > >::operator+(int const&) const
1.23 51.88 0.72 70188877 0.00 0.00 __gnu_cxx::__normal_iterator<int const, std::vector<int, std::allocator<int> > >::difference_type __gnu_cxx::operator-<int const*, int const*, std::vector<int, std::allocator<int> > >(__gnu_cxx::__normal_iterator<int const*, std::vector<int, std::allocator<int> > > const&, __gnu_cxx::__normal_iterator<int const*, std::vector<int, std::allocator<int> > > const&)
1.21 52.59 0.71 70188877 0.00 0.00 std::vector<int, std::allocator<int> >::size() const
1.02 53.19 0.60 53137621 0.00 0.00 std::vector<std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >, std::allocator<std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > > >::operator[](unsigned)
0.99 53.77 0.58 70190426 0.00 0.00 std::vector<int, std::allocator<int> >::end() const
0.85 54.27 0.50 40438352 0.00 0.00 Engine::inField(int, int)
0.82 54.74 0.48 140380852 0.00 0.00 __gnu_cxx::__normal_iterator<int const*, std::vector<int, std::allocator<int> > >::__normal_iterator(int const* const&)
0.77 55.20 0.45 140380852 0.00 0.00 __gnu_cxx::__normal_iterator<int const*, std::vector<int, std::allocator<int> > >::base() const
0.72 55.62 0.42 70190426 0.00 0.00 std::vector<int, std::allocator<int> >::begin() const
0.68 56.02 0.40 106275242 0.00 0.00 __gnu_cxx::__normal_iterator<std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >, std::vector<std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >, std::allocator<std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > > > >::__normal_iterator(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&)
0.51 56.31 0.30 53137621 0.00 0.00 std::vector<std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >, std::allocator<std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > > >::begin()
0.51 56.62 0.30 974821 0.00 0.00 Engine::moveForward(int, int)
0.41 56.85 0.24 53137621 0.00 0.00 __gnu_cxx::__normal_iterator<std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >, std::vector<std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >, std::allocator<std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > > > >::operator() const
0.39 57.09 0.23 974818 0.00 0.00 Engine::moveBackward(int, int)
0.22 57.22 0.13 23066 0.00 0.00 Engine::findMoveList(bool, int)
0.19 57.33 0.11 808770 0.00 0.00 std::_Rb_tree<int, std::pair<int const, int>, std::_Select1st<std::pair<int const, int> >, std::less<int>, std::allocator<std::pair<int const, int> > >::insert_equal(std::pair<int const, int> const&)
0.17 57.42 0.10 17546872 0.00 0.00 __gnu_cxx::__normal_iterator<std::vector<int, std::allocator<int> > const*, std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > >::__normal_iterator(std::vector<int, std::allocator<int> > const* const&)
0.17 57.52 0.10 8773426 0.00 0.00 __gnu_cxx::__normal_iterator<std::vector<int, std::allocator<int> > const*, std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > >::difference_type __gnu_cxx::operator-<std::vector<int, std::allocator<int> > const*, std::vector<int, std::allocator<int> > const*, std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > >(__gnu_cxx::__normal_iterator<std::vector<int, std::allocator<int> > const*, std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > > const&, __gnu_cxx::__normal_iterator<std::vector<int, std::allocator<int> > const*, std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > > const&)
0.17 57.63 0.10 3944325 0.00 0.00 std::less<int>::operator()(int const&, int const&) const
0.14 57.70 0.08 8773436 0.00 0.00 std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >::end() const
0.14 57.78 0.08 1949639 0.00 0.00 std::vector<bool, std::allocator<bool> >::operator[](unsigned)
0.14 57.87 0.08 std::_Rb_tree_insert_and_rebalance(bool, std::_Rb_tree_node_base*, std::_Rb_tree_node_base*, std::_Rb_tree_node_base&)
0.10 57.92 0.06 8773436 0.00 0.00 std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >::begin() const
0.10 57.98 0.06 808770 0.00 0.00 Engine::setTurn(int, int, int, int, int, int)
0.09 58.04 0.06 3 0.02 0.02 Engine::start()
...so wie es aussieht geht die meiste rechenleistung für die vectoren drauf?!
wenn ich jetzt die vectoren durch arrays ersetze, wird es was bringen?ich brauche eigentlich nur feste arrays, die größe muss zur laufzeit nicht geändert werden. allerdings wird der std::vector<int>::operator[] einige male aufgerufen. 1162099204 mal in einer minute, um genau zu sein.
also lohnt sich der aufwand oder ist es, wenn ich arrays verwende doch nur um ein paar prozent schneller?
ich benutze haufenweise 3-dimensionale vectoren, ist es vielleicht deswegen so langsam?seltsam ist, ich mache auch exzessiv gebrauch von ganz vielen std::multimap's, diese tauchen aber erst irgendwo ganz unten in der liste auf. und machen keine 0,1% der rechenleistung aus.
ich bin für jeden tip zur wahl eines anderen containers/datentyps/array-typs zu haben.
-
borg schrieb:
so wie es aussieht geht die meiste rechenleistung für die vectoren drauf?!
wenn ich jetzt die vectoren durch arrays ersetze, wird es was bringen?direkt erstmal nix.
der op[] ist nicht schneller oder lahmer als der auf zeigern (außer, es ist ein vector<bool>).kannst aber effekte kriegen, weil der speicher im freispeicher liegt und nicht auf dem stack und weil der freispeicher mehr interne fragmenterung kennt(evtl ein paar mal mehr paging). kann effekte haben, fall op[][] verwendet wird und bei festen größen, die zweierpotenzen sind, <<(shifrt) statt *(plutimikation) oder *(indirektion) genommen werden kann.
aber sonst nix.
-
Sieht für mich aus, als hättest du nen Debug-Build getestet. Den op[] sollte es im Release-Build eigentlich nicht mehr geben.
-
Optimizer schrieb:
Sieht für mich aus, als hättest du nen Debug-Build getestet. Den op[] sollte es im Release-Build eigentlich nicht mehr geben.
wenns im debug-modus war muss es irgendwie ins makefile gekommen sein, ich wars nicht
ich habs jetzt mal von hand kompiliert, mit allen optimierungen die der g++ hergibt und -pg für die profiler-informationen. jetzt siehts so ausFlat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
83.59 2.14 2.14 550960 0.00 0.00 Engine::evaluatePosition(bool)
4.30 2.25 0.11 564930 0.00 0.00 Engine::moveForward(int, int)
3.52 2.34 0.09 564928 0.00 0.00 Engine::moveBackward(int, int)
2.73 2.41 0.07 465995 0.00 0.00 std::_Rb_tree<int, std::pair<int const, int>, std::_Select1st<std::pair<int const, int> >, std::less<int>, std::allocator<std::pair<int const, int> > >::insert_equal(std::pair<int const, int> const&)
1.56 2.45 0.04 13970 0.00 0.00 Engine::findMoveList(bool, int)
1.17 2.48 0.03 465995 0.00 0.00 std::_Rb_tree<int, std::pair<int const, int>, std::_Select1st<std::pair<int const, int> >, std::less<int>, std::allocator<std::pair<int const, int> > >::_M_insert(std::_Rb_tree_node_base*, std::_Rb_tree_node_base*, std::pair<int const, int> const&)
0.78 2.50 0.02 std::_Rb_tree_insert_and_rebalance(bool, std::_Rb_tree_node_base*, std::_Rb_tree_node_base*, std::_Rb_tree_node_base&)
0.39 2.51 0.01 465995 0.00 0.00 Engine::setTurn(int, int, int, int, int, int)
0.39 2.52 0.01 13970 0.00 0.00 std::_Rb_tree<int, std::pair<int const, int>, std::_Select1st<std::pair<int const, int> >, std::less<int>, std::allocator<std::pair<int const, int> > >::_M_erase(std::_Rb_tree_node<std::pair<int const, int> >)
0.39 2.53 0.01 _Unwind_SjLj_Register
0.39 2.54 0.01 std::_Rb_tree_rotate_left(std::_Rb_tree_node_base, std::_Rb_tree_node_base*&)
0.39 2.55 0.01 operator delete(void*)
0.39 2.56 0.01 operator new(unsigned)
...schneller ist es trotz dem optimierungen nicht geworden.
aber interessant ist zum einem die funktion evaluatePosition(bool), sie sticht jetzt doch arg hervor und zum anderem die ganzen std::pair<...> aufrufe, kommen die von der std::multimap? ich benutz std::pair eigentlich gar nichtleider besteht evaluatePosition nur aus nen paar if-abfragen und ner menge switches, da kann ich nicht viel an der geschwindigkeit drehen. die menge der aufrufe machts halt
-
borg schrieb:
leider besteht evaluatePosition nur aus nen paar if-abfragen und ner menge switches, da kann ich nicht viel an der geschwindigkeit drehen. die menge der aufrufe machts halt
hier lohnen sich uU micro optimierungen. wie zB die labels nach der wahrscheinlichkeit wie oft sie angesprungen werden ordnen. etc.
kannst ja mal die funktion posten, vielleicht faellt ja jemandem ein trick ein was man besser machen kann
-
Optimizer schrieb:
Sieht für mich aus, als hättest du nen Debug-Build getestet. Den op[] sollte es im Release-Build eigentlich nicht mehr geben.
vector hat keinen op[] im Release
Wie kommt das?Ja, eine std::multimap verwendet intern std::pair<>'s... vielleicht solltest du den Algorithmus ueberdenken, wenn sich sonst nix mehr optimieren laesst
-
Blue-Tiger schrieb:
Optimizer schrieb:
Sieht für mich aus, als hättest du nen Debug-Build getestet. Den op[] sollte es im Release-Build eigentlich nicht mehr geben.
vector hat keinen op[] im Release
Wie kommt das?Inlining
-
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.