Citat:
Ursprungligen postat av
kakelpanna
Jag har fått förslaget att det går snabbare att generera moves om schackbrädan är en array istället för map, stämmer det? Att man går igenom alla 64 rutor och genererar moves för relevanta rutor, istället för att iterera över en map av aktuell spelares pjäser. Det dröjer en del innan jag kan testa det, men vad tror du?
Jag provade det du skrev och resultatet var detsamma. Ialllafall inte märkbar.
I båda fallen får jag samma tid för det här testet, ena gången med array av piece values i score() där pjäserna är enum-ints ints och kollas upp med pieceValue[piece]. Andra försöket är med map av pieceValues.
ChessBoard test;
test.reset();
size_t t=time(0);
test.AIMove();
t=time(0)-t;
cout<<t<<endl;
return 0;
Båda ger 6 sekunder, mapen ger 6 och bara ibland 7. Jag provade att göra sökträdet djupare. För minimax med djup 6 istället för 5.. så fick jag: 168 sekunder med map, 156 sekunder med array.
Som jag skrev innan, börja med att få programmet att fungera som du vill. Algoritmmässiga förbättringar som leder till att du behöver besöka färre noder vinner alltid över kodoptimeringar. Det är först när du inte kommer längre med algoritmerna som du kan vinna något på att slipa på detaljer. Gör man tvärtom så riskerar man att tidigt hamna i kod som är svår att ändra och därför är svår att förbättra.
Eftersom datamodellen som representerar ett schackspel går att göra extremt kompakt så vinner du antagligen på att skapa representationer som gynnar algoritmernas flöde, även om det leder till en viss redundans. Antagligen vill du både kunna iterera över schackbrädets rutor och över spelets pjäser beroende på vad du skall göra. I princip kan du representera brädet med en array på 64 bytes. För varje ruta behöver du 1 bit som talar om ifall den är tom eller inte, 1 bit som talar om färgen på pjäsen och 5 bitar för vilken pjästyp som står där (kung, dam, löpare, häst, torn eller bonde). Vill du sedan kunna iterera över pjäserna så kan du ha en annan array på 32 bytes som talar om vilken ruta varje pjäs står på och krympa storleken när pjäser försvinner. Åtminstone i slutspelet så kan det vara en fördel medan det inte gör så stor skillnad i början.
Eftersom det verkar råda en viss förvirring om standardkontainrarna så ser det ut så här i C++:
std::set/std::map - implementerade genom rödsvarta träd. Ett set eller en map bäddar in en pekare till en rot-nod och varje nod bäddar in ett element plus pekare till förälder samt vänster och höger barn.
std::unordered_set/std::unordered_map - implementerade genom hashtabeller. Ett set eller en map bäddar in en pekare till en array av länkade listor där varje listnod bäddar in ett element plus en pekare till nästföljande nod.
std::vector<T> - bäddar in en pekare till en dymaniskt allokerad array av godtycklig storlek.
std::array - bäddar in en array av element. std::array<T, n> är i princip samma som T[n].
Betrakta följande kodexempel:
Kod:
const std::map<int, int> a = {{ 1, 0}, {2, 0}, ...};
const std::map<int, int> b = {{ 1, 1}, {2, 2}, ...};
int x = a[0];
Även om kompilatorn skulle kunna förstå hur trädet
a ser ut så kan den inte vid kompileringstillfället lista ut vilket värde
x skall få, utan den måste köra en dyr trädsökning för att hämta ut värdet. Ett oöverstigligt problem för kompilatorn är att
a och
b pekar ut dynamiskt minne av samma typ och att kompilatorn därför inte kan veta om den skriver över
a:s noder när den initierar noderna i
b. Const-deklarationen gäller bara
a och
b, inte noderna som implementerar
a och
b.
Jämför med följande:
Kod:
const int a[] = { 0, 0, 0, ... };
const int b[] = { 1, 2, 3, ... };
...
int x = a[0];
if (x == 1) foo();
Vi talar om för kompilatorn att
a och
b är konstanta arrayer vars värden inte går att ändra. Kompilatorn kan redan vid kodgenereringen se att
x får värdet
0 och att den inte ens behöver generera anropet till foo() eftersom man aldrig kan komma dit.
I slutänden gör sådana här skillnader genomslag i körtiden. Men skriv programmet först och gör sedan profileringar. Då hittar du vad som faktiskt tar tid och kan åtgärda de viktigaste sakerna först. Ofta spenderar programmet tiden på helt andra ställen än vad man trodde innan.
