Sortering av dragen
Allmänt
En mycket viktig detalj i draggenereringen är själva sorteringen av dragen så att viktiga drag testas före oviktiga drag. Att detta är viktigt hänger intimt ihop med hur alfa-beta -reduceringen arbetar (beskrivet under avsnittet sökfunktion).



Vad det handlar om är allstå att placera drag överst i draglistan som på olika sätt ökar chansen till betaklipp i sökträdet. Om du tittar på bilden ovan så vill vi alltså helst att alla viktiga drag skall ligga först, testas först. Ett betaklipp är ju som jag beskrivit under sökning ett klipp i trädet där helt onödiga drag sorteras bort. Om din motspelare hotar din drottning så är naturligtvis alla de drag som inte flyttar drottningen onödiga att överväga. Det kan man åtminstone antaga. Det enda rimliga är att flytta undan drottningen. Dragsorteringen lär/får datorn att resonera på samma sätt.

Exempel: Med och utan sortering
Här nedan till vänster ser du en enkel situation i ett schackspel. Uppställningen är helt overklig men det jag vill visa är själva sorteringen.
Osorterad  Sorterad
VitSvart
De5
Df5
Dg5
Dh5
Dc5
Db5
Da5
Dd4
Dd3
Dxd2
Dd6
Dd7
Dd8
Dxe4
Dc4
Db3
Dxa2
De6
Dc6
h6
h5
g6
g5
f6
f5
e6
e5
c6
c5
b6
b5
a6
a5
Sh6
Sf6
Kd8
Kd7
Ld7
Le6
Lf5
Lg4
Lh3
Sc6
Sa6
Sd7
Sh3
Sf3
Se2
Le2
Ld3
Lc4
Lb5
La6
Ke2
De2
Df3
Dg4
Dh5
Sc3
Sa3
h3
h4
g3
g4
f3
f4
d3
d4
c3
c4
b3
b4
a3
a4
exd5
e5
VitSvart
Dxe4
h5
b5
a6
De5
Dg5
Dc5
Da5
Dd4
Dd6
Dd7
Dd8
De6
Dc6
h6
g6
g5
f6
f5
e6
e5
c6
c5
b6
a5
Sh6
Sf6
Kd8
Kd7
Ld7
Le6
Lg4
Sc6
Sa6
Sd7
Df5
Lf5
Lh3
Dh5
Db5
Dd3
Dc4
Db3
Dxd2
Dxa2

exd5
d3
c4
h3
g4
Sh3
Sf3
Se2
Le2
Ld3
Lc4
Lb5
Ke2
De2
Df3
Sc3
Sa3
h4
g3
f3
f4
c3
b4
a3
a4
d4
b3
e5
La6
Dg4
Dh5
Till höger ser du en lista av möjliga drag för svart och vit i situationen dels då dragen kommer direkt från draggeneratorn och dels efter att ha blivit sorterade. (Detta är verklig utdata från dragsorteringen som beskrivs nedan på denna sida, vilket samtidigt visar att algoritmerna fungerar bra)

När dragen är osorterade så blir ordningen på dragen slumpmässig; eller snarare präglad av den ordning som blir följden av den algoritm som implementerar draggeneratorn. I detta exempel kommer alltså sökfunktionen att först flytta omkring på drottningen (röd linje i bilden) horisontellt och sen vertikalt. Först därefter kommer sökfunktionen prova att slå ut bonden. Rent intutivt är ju denna ordning ganska inneffektiv. Kan vi slå ut en pjäs så är ju det naturligtvis det som är mest intressant. Det är inte säkert att det är det bästa draget - men det är mest intressant att testa först. Notera också hur dragen för svart ser ut osorterade. Det mest uppenbara här vore ju att först testa att slå ut drottningen. Men istället vill den testa vad som händer om man flyttar fram hästarna och kör ut med löparen. Alternativet att slå ut drottningen råkar t.o.m. hamna bland de sista saker datorn överväger. Inte så effektivt! Det kommer ta lång tid för sökalgoritmen att hitta rätt med denna kaotiska oordning.

Jämför nu med den sorterade listan. För både vit och svart ligger dragen överst där de slår varandras pjäser. Detta kommer bli det första sökfunktionen testar. Speciellt är det oerhört viktigt att bondens slag mot drottningen ligger överst i svart's draglista. Varför? Därför att detta kommer generera ett betaklipp för alla vita drag som inte flyttar drottningen. När sökalgoritmen provar att flytta någon annan pjäs kommer den direkt vid första svarta motdraget se att drottningen ryker och då kan den direkt avbryta sökningen där och istället prova något annat. Alternativet är att den provar en mängd mer eller mindre komplexa rörelsemönster baraför att lång senare, när kopiösa mängder tid slösats bort, komma fram till att drottningen blir utslagen och all sökning är gjord i onödan. Lägg också märke till att samtliga drag som resulterar i att drottningen direkt blir utslagen (orange markering) ligger i botten. Dessa drag är alltså mest onödiga att testa eftersom drottningen blir utslagen ifall något av dessa drag görs.



Prioritering
Sorteringen av dragen handlar inte enbart om att placera attackerande drag överst. Man kan finna fler saker att sortera kring. Jag kommer att använda följande prioritering när dragen skall sorteras. Dragsorteringens roll är alltså att ta listan med legala drag och försöka göra en kvalificerad gissning vilket eller vilka drag som är viktiga att testa först. Vissa beslut är enkla och relativt uppenbara. Det gäller t.ex. 1 och 2 i listan medans nummer 3 är ganska avancerad.

Skillnaden med och utan att försöka gissa vilka drag som är viktiga gör mycket stor tidsskillnad vid sökningen. Om dragsorteringen kan göra en bra gissning så behövs bara lite sökning för att säkerställa att det verkligen är ett bra drag. Om gissningen är dålig eller obefintlig då kommer sökfunktionen leta i all evighet för att hitta ett bra drag.

Dragsorteringen gör som sagt enbart en kvalificerad gissning. I bästa fall är denna gissning så bra att det inte behövs någon sökfunktion. Vi kan spela gissningen direkt. Detta är helt omöjligt att uppnå. Ibland kommer denna gissning bli bra - ibland dålig. Men ju bättre vi gör denna sortering desto bättre kommer programmet spela schack.

Sorteringstekniker för attackerade pjäser
Olika tekniker som man kan använda för att sortera draglistan inkluderar t.ex.

Problemet med den första av dessa tekniker kan exemplificeras med följande: Ponera att en torn kan slå ut en häst. Denna häst är garderad av en bonde. Är det meningsfullt att slå ut denna häst? Knappast, då går ju tornet förlorat. Vi kommer alltså inte tjäna någonting på att prioritera upp ett sådant drag.

Problem av denna typen skapade SEE. Genom att försöka analysera/förutspå om en pjäs är garderad eller inte kan denna typen av misstag undvikas.

Lite mer konkret vad som menas med SEE förutom ovan resonemang är svårt att hitta. Det verkar som definitionen flyter lite. Jag har här uppfunnit något helt eget enligt min tolkning av vad tekniken handlar om, där varje ruta ges attackvärden som representerar de pjäser av båda färger som hotar positionen. Läs längre ner.

Den kod jag skapat för dragsorteringen använder alltså egna tolkningar av båda dessa koncept ovan (MVV/LVA och SEE) samt egna teorier som jag redovisar här nedan. Först ges dragen en poäng utifrån matrialdifferensen mellan den som slår och blir slagen, därefter, om det är nödvändigt, så korrigeras dessa värden utifrån studier av hur rutor attackeras/garderas. Två matriser med positionella och vektoriella attackvärden hjälper till med analysen.

Drag i datorns bästa linje
Denna linje brukar kallas "principal variation" (PV) eller "main variation". Det är helt enkelt den serie av optimala drag och optimala motdrag som leder fram till det bästa alfa-värdet när datorn gjort sin sökning.

Säg att vi låter sökfunktionen leta efter bästa drag 1 ply fram. Dvs, det drag som ger bästa alfa-värdet.

Svaret blev: 1. Td8

Detta är PV -linjen som i detta fall bara är ett drag. Nu vill vi göra om samma sökning fast 3 ply fram.

Svaret blev kanske: 1. Td8 Dxb5 2. Dd6

Gissa? Vi gör om samma sökning fast 5 ply fram.

Svaret blev kanske: 1. Td8 Dxb5 2. Dd6 Lxf2+ 3. Hxf2

Dvs, Td8 är fortfarande (optimal situation) det bästa draget. Det bästa motdraget är Dxb5 osv. Många gånger är det så att denna linje i en liten del av partiet vid en sökning är någorlunda stabil. I de situationer då den är någorlunda stabil kan vi optimera sökningen genom att låta draggeneratorn placera dessa drag överst i draglistan. Vi börjar alltså med att testa om draget i PV -linjen fortfarande är bästa draget. Om så inte skulle vara fallet är ingen skada skedd. Men om så skulle vara fallet, vilket är fullt tänkbart, i vissa fall tom sannolikt, kan vi skippa en del sökning vilket sparar tid.

Den algoritm som skapar denna lista är alltså sökfunktionen (se längre ner). Vi använder sen denna lista i draggenereringen. Att vi sorterar dragen så att detta bästa drag drag ligger först spelar en central roll för att få iterativ fördjupning att arbeta optimalt. För varje ytterligare djup längre ner kommer sökfunktionen då oftast att gå direkt till det nya djupet och söka där - utan att göra om sökningarna på grundare djup (se figur till höger, nedan).

Om man tänker sig ett parti där spelarna ömsom gör sina drag. Vit (V) börjar och svart (S) följer, vi indexerar med ply.
V1 S2 -> V3 S4 -> V5 S6 -> ...
Man kan tänka sig denna linje med drag var som helst i partiet och generalisera:
Vn Sn+1 -> Vn+2 Sn+3 -> Vn+4 Sn+5 -> ...
Teorin här är att när vi gör en sökning så sparar vi denna linje så djupt som vi söker. Säg att vi gör en sökning D ply fram. När sökningen är klar har vi PV -linje som ser ut så här.
Vn Sn+1 ... Vn+d-1 Sn+d
När vi anropar draggeneratorn från sökfunktionen skickar vi med djupet. Vidare hämtar vi i draggeneratorn upp draget från PV -linjen på exakt det djupet vi befinner oss och placerar detta drag överst i draglistan. Exempel: Om sökalgoritmen hämtar alla legala drag för Vit spelare 2 ply fram lägger vi helt enkelt draget Vn+2 överst i draglistan genom att ge det så mycket poäng att det garanterat är överst. Jag ger draget 10.000 poäng vilket är högsta poäng.

I draggenereringen testar helt jag helt enkelt om draget ligger i PV -linjen (pvlFr/pvlTo) på aktuellt djup (dp).

if ((pvlTo[dp]==ox)&&(pvlFr[dp]==fpos))
{
	pvp=10000;
}
m_moveSort[m_sp]=pvp;
Enkelt och klart som korvspad. Denna optimering fungerar ofta men inte alltid. Har man otur varierar bästa draget kraftigt med djupet man söker på. Detta kan vara fallet i en situation som präglas mycket av horisonteffekter, där saker ser mycket annorlunda ut för varje ökning av sökdjupet. Nedan har jag klippt in lite kod som visar var någonstans i Negamax som PV -linjen skapas (grön kod), vilket alltså är där bästa alfa-värdet hittats. Läs mer om detta under sökning.

function NegaMaxAlfaBeta(var depth, var alfa, var beta)
{
	if (depth == 0)
	{
		return Eval();
	}
	Skapa en lista av alla drag
	while (drag kvar att göra)
	{
		Gör ett drag i listan
		val = -NegaMaxAlfaBeta(depth - 1, -beta, -alfa);
		Ta tillbaka draget
		if (val >= beta)
		{
			return beta;
		}	
		if (val > alfa)
		{	
			alfa = val;
			pvlFr[depth]=från position
			pvlTo[depth]=till position
		}
	}
	return alfa;
}

Senast slagna pjäs
Ide´n här är att en pjäs som blir slagen oftast är en del i ett pjäsutbyte. Genom att börja med att testa denna tes så ökar sannolikheten att vi hittar ett beta -klipp i trädet. Vi får snabbt reda på vad som händer när vi slår ut en pjäs. Denna finess är enkel att implementera. Det enda vi behöver göra är att minnas senast utslagna pjäs. Hittar vi en sådan pjäs när vi genererar dragen ger vi denna pjäs extra mycket poäng så att den hamnar högt i draglistan.

Anfallande drag
Minst värt anfaller mest värd
När det gäller intern sortering av attackerade drag är denna ordning ganska intutiv. Kan vi slå ut en drottning med en bonde så provar vi det före vi testar att slå ut en bonde med en drottning. Vi rangordningar attackernade drag efter materiell skillnad mellan den som blir anfallen och den som anfaller. Bilden illustrerar i vilken ordning det är önskvärt att analysera dragen.

Denna formel som rangordningar dragen fungerar tillsammans med nedan beskrivna attackvärden enligt.
Poäng = vfm(anfallen position) - matrial(pjäs som anfaller)
Där vfm är det matriella värdet som erövras eller förloras efter att hänsyn tagits till hur rutan är attackerad/garderad av båda sidor.

Positionella attackvärden
För att genereringen av drag skall bli korrekt behöver vi information ifall en ruta är hotad eller inte. Detta för att hantera följande regelsituationer.

Detta sagt återstår också problemet med att sortera efter pjäser som slår ut varandra. Det var det som var huvudspåret i detta avsnitt. Vi vill alltså lösa 2 problem på samma gång här.

Vi behöver ett effektivt sätt att hålla koll på om pjäser eller rutor är hotade. För detta ändamål har jag skapat en matris lika stor som spelplanen vars uppgift är att hålla koll på hotade positioner.

Ett intressant moment 22 uppstår här. Det mest naturliga sättet att ta reda på ifall en ruta är hotad är naturligtvis att fråga draggeneratorn. Men för att räkna ut alla drag korrekt måste draggeneratorn veta vilka rutor som är hotade.

Räddningen kommer från oväntat håll, en ren tillfällighet. Eftersom draggeneratorn anropas varannan gång med uppdraget att räkna ut drag för vit resp. svart kan lägga upp koden så här.

Samtidigt som vi räknar ut dragen bygger vi alltså upp en matris med attackvärden. Dessa attackvärden används dels för att få legala drag och dels för att sortera draglistan.

Varje position i matrisen med attackvärden är ett 8-bitars heltal med följande struktur (se bild till höger). Jag använder bit-operationer för att flagga rätt bit i detta heltal. De flaggor som jag sätter beror på vilken pjäs och färg som hotar/garderar positionen (beror på vilket perspektiv man har).

En intressant fråga är hur dessa värden skall användas och tolkas. Det finns några enkla uppenbara situationer. Om vi tänker oss en drottning som kan slå ut en bonde. Detta drag har blivit upp-prioriterat eftersom vi testar drag som slår ut pjäser före alla andra drag. Men ponera att denna bonde är garderad. Då är ju draget antagligen helt värdelöst. Vi vill ju inte bli av med drottningen. Denna situation är enkel. Om en pjäs med högt matrialvärde anfaller en med lågt matrialvärde då får inte den pjäs som attackeras vara garderad - då är draget kasst - och då korrigerar vi poängen nedåt så att draget prioriteras ner.

Sen finns det några situationer när en ruta kan vara garderad men där det fortfarande är intressant att slå ut pjäsen. Ponera den omvända situationen. Vi har en bonde som kan slå ut en drottning. Drottningen är förvisso garderad men so what! Vi slår ut fiendens drottningen och förlorar samtidigt en bonde. Det är fortfarande ett bra byte. Dessa två exempel på ytterligheter är ganska enkla. I det första faller korrigerar vi poängen kraftigt ner så att draget prioriteras ner och i det andra faller kan vi låta poängen stå kvar eller kanske t.o.m. ge en viss bonus så att draget prioriteras upp.

Informationen om vad som attackerar en position eller pjäs på en viss position blir ganska stor. Vi kan avgöra hur värdefull en pjäs som attackerar en ruta är och vi kan i viss mån avgöra hur många pjäser som attackerar en ruta. Man kan ju tänka sig situationen där flera pjäser från båda sidor attackerar en ruta. Hur skall ett drag till en sådan hotad/garderad position värderas? Uppenbart är ju att ett sådant drag potentiellt leder till en hel del pjäsutbyte på den positionen. Detta är ju i sig inget problem, sålänge vi vinner. Detta leder osökt in på en generalisering av problemet.

Klart som korvspad. Men när vi ändå sitter på en massa värdefull information är det nästan tjänstefel att inte använda denna information fullt ut. Här kommer mer förslag på prioriteringar.

Vektoriella attackvärden
Det finns en del begränsningar med ovanstående attackvärdesystem; det fokuserar enbart på attackerade positioner. Men hur gör vi med positioner som ligger gömda bakom vissa pjäser? Dessa kommer inte få några positionella attackvärden eftersom ingenting attackeras där. Vi måste introducera att system för att kunna spåra det man helt enkelt kallar garderade/attackerade pjäser och då avses inte positionen utan vektorn, dvs i den riktning en pjäs är garderar/attackerad.

Studera bilden till höger. Svart bonde kan flytta 2 steg fram. Vad händer på den positionen? Vi kan studera attackvärden för positionen ifråga och konstatera att positionen bevakas av en drottning. Vad betyder det? Det borde betyda att vi blir av med vår bonde. Men samtidigt ser vi ju att där finns ett svart torn som garderar bonden. Om drottningen skulle slå ut bonden, då tar vi drottningen med tornet. Ett ganska bra pjäsbyte!

För att kunna täcka in pjäser som är garderade trots att de rör sig behöver vi ytterligare information utöver våra attackvärden.

Vi behöver information om i vilka riktningar en pjäs är garderad. För detta ändamål inför jag ytterligare en matris lika stor som spelbrädan där varje position är ett 8-bitars heltal där bit-positionerna representerar i vilken riktning en pjäs kan röra sig och fortfarande vara garderad. Observera att attackvärden som jag tidigare pratat om relaterar till en viss position. Den vektoriella attackmatrisen relaterar till pjäser. Det är pjäsen som äger denna information. När pjäsen flyttar så låter vi helt enkelt denna information följa med.

Mer exakt har bitpositionerna fått följande betydelse (se bild till vänster).

Om vi nu studerar ovanstående exempel där bonden flyttar fram 2 rutor en gång till, så har denna gång bonden ett vektoriellt attackvärde som berättar för oss en den är garderad i den fil där bonden rör sig. Det innebär att vi även kan ta hänsyn till denna information i scenariot där drottningen slår ut bonden.

Analysera attackvärden
Det som är nämt ovan måste ju på något sätt översättas i konkret kod. Om vi börjar med positionella attackvärden; vad innebär det alltså att en viss ruta är attackerad av olika pjäser? För att strukturera tänkandet lite kan man göra följande tabell för några exempel.

Ponera att vi tänker flytta en vit bonde till en position. Denna tänkbara position kan då tänkas vara attackerad med med följande pjäser (den kan vara attackerad med ännu fler pjäser, detta är bara ett exempel).

Till att börja med måste vi konstatera att positionen är attackerad av en vit bonde. Om detta är bonden vi tänker oss ska flytta dit eller någon annan bonde vet vi inte. Jag har därför markerad denna rad med rött då den är okänd.

Vi kan resonera så här och samtidigt fylla i tabellen:

- Om vi flyttar vår vita bonde till en position garderad av en svart bonde, häst, torn eller drottning då kan vi utgå ifrån att vi blir av med bonden. Jag ger dessa positioner -100 poäng vilket reflekterar värde på bonden som vi kan anta är förlorad vid en flytt till denna position.

- Flyttar vi vår vita bonde till en position garderad av en vit häst blir vi antagligen inte av med vår bonde. Men blir vi det kan vi plocka motspelarens pjäs. Jag ger dessa positioner poäng utifrån vilken pjäs vi kan ta från motspelaren för att kompensera förlusten. Poängen är alltså slutsumman i vinst/förlust efter matrialbytet. Går vi fram med bonden som sen blir utslagen av en häst och vi därefter plockar hästen så har vi ju vunnit en häst men blivit av med en bonde. Rent matriellt har vi vunnit det slaget.

-100-100-100-100
X-100-100-100-100
Y0200400900
Z0200400900
A0200400900
Ponera vidare att vi har en vit häst som vi skall flytta till en position som kan vara attackerad av följande pjäser.

Man kan resonera som vi gjorde tidigare. Är positionen garderad av svart pjäs kan vi anta att den vita hästen är förlorad. En skillnad från ovan exempel är att om vår vita häst är garderad av en egen pjäs så krävs ju att vi kan plocka en pjäs från utmanaren som är mer värdefull än den vi blev av med för att det skall vara ett bra byte.

Okej, det börjar klarna hur dessa värden ser ut för tornet och drottningen också. Vi kan alltså översätta dessa attackvärden till en positiv eller negativ bonus som i princip motsvarar det vi kan tjäna eller förlora i matrialvärde ifall vi flyttar till positionen ifråga.

-300-300-300-300
X-2000200700
Y-300-300-300-300
X-2000200700
X-2000200700
Nu kan ju situationen vara mer komlex än dessa exempel. En position kan ju vara attackerad med flera pjäser från båda sidor. Dessutom kanske man inte vill göra femtioelva sådana här tabeller för hand. Det kommer nämligen blir tusentals värden att hålla reda på.

En annan intressant fråga i sammanhanget är vilka bonusvärden vi skall ge för att flytta vår vita bonde till en position som är garderad av någon annan vit pjäs. Uppenbart är ju att det är en trygg position men samtidigt skall ju inte dessa värden konkurrera med viktigare bonus.

Begränsningar i attackanalysen
Innan jag beskriver hur själva koden för att räkna ut materiell vinst eller förlust givet ett attackvärde ser ut något om begränsningar och konsekvenser. Det är viktigt att veta att dessa begränsningar finns annars kan viss förvirring uppstå hur sorteringen fungerar.

Om man påminner sig hur variabeln som håller koll på attackerade pjäser ser ut kan man konstatera att den kan mäta 4 olika pjäser på vardera sidan. Vi vet inte om en ruta attackeras av flera olika bönder. Inte heller kan vi skilja på en häst eller löpare eller om flera av dessa pjäser attackerar en ruta. Däremot ser vi hur olika matrial m.a.p. dessa värde attackerar/garderar en ruta.

Matrisen med attackvärden är konstruerad för att kunna skapas snabbt samtidigt som draggeneratorn räknar ut alla legala drag. Det är ett medvetet val att den i första hand skall vara lätt uträknad. Alternativet är nämligen att vi får en komplicerad kod som gör draggeneratorn långsam och det känns inte speciellt bra.

Priset för att snabbt kunna skapa denna attackmatris är att den ger en ungefärlig bild av verkligheten med ett antal brister. Detta är ingen kritisk brist som dramatiskt äventyrar programmets spelkvalite. Bristerna kommer resultera i att programmet i vissa fall går vissa omvägar för att bedöma ett drag. Begränsningen innebär att draglistan inte sorteras optimalt, dvs sökfunktionen kommer få lite mer att göra ibland. Bedömningen är ändå att det är mycket mer plus än minus.

En avancerade fullständigt analys av dessa attackvärden blir mycket mer långsam vilket ifrågasätter hela sorterings-projektet m.t.p. att dess syfte just är att snabba upp sökningen.

En annan aspekt är också att det är osannolikt att en viss position är attackerad av väldigt många pjäser från båda sidor. Tar man bönderna t.ex. så kan ju inte en ruta vara attackerad av fler än högst 2 bönder. Det är också osannolikt att en ruta är attackerad av 2 löpare. Av den enkla anledningen att det är teoretiskt omöjligt då den ena rör sig på svarta och den andra på vita rutor. Den eventuella "skadan", i den mån detta synsätt är relevant, av en ofullständig analys begränsas alltså till viss del av olika uppenbara sannolikheter.

Studera bilderna nummer 2 (mitten) och 3 (nederst) här till vänster. Nummer 2 illustrerar en logisk följd som striden av pjäser borde följa som ger en materiell neutral utgång. Men denna kommer inte systemet kunna identifiera eftersom bara en av bönderna är synliga. Det som kommer synas är istället det som bild 3 illustrerar. I praktiken vore scenario 3 katastrof eftersom det kommer sluta med att vi blir av med drottningen. Men nu är detta bara en statisk evaluering för att sortera i vilken ordning pjäserna skall testas av sökfunktionen; så sökfunktionen kommer hitta rätt ändå ifall denna situation skulle uppstå fast med lite extra ansträngning.

Översätta attackvärden till materiell vinst/förlust
Varje attackvärde har en direkt motsvarighet i materiell vinst/förlust. Det är sistnämda vi är intresserade av eftersom vi kan använda detta värde direkt i dragsorteringen. Ett positivt värde betyder ju att vi antagligen (gissning) vinner en strid på en viss position. Ett negativt värde betyder antagligen (gissning) att vi förlorar en strid på en viss position. Eftersom attackvärdet med informationen om båda sidors attacker på en ruta upptar 8 bitar betyder detta att det finns 255 attackvärden. Vi kan räkna ut dessa i förväg och behöver då bara hämta värdet när dragsorteringen så önskar.

Vad jag gör är helt enkelt att testa alla tänkbara kombinationer av vita och svarta pjäser (bonde, häst/löpare, torn och drottning) som kan attackera en ruta. Dessa kombinationer låter man sedan kriga mot varandra enligt förutsättningen att spelaren alltid attackerar med den billigaste pjäsen som finns att tillgå. Poängen detta resulterar i motsvarar det materiella överskott eller underskott som blir resultatet efter ett sådant här slag. Denna poäng stoppar jag i en lätt åtkomlig tabell som sedan kommer användas i draggeneratorn. Koden som gör jobbet blir som följer ....

Kod för att skapa översättartabellen
function createAttackTable(m)
{
   var b,w,t,p,w_bb,b_bb,w_iv,b_iv,black_bits,white_bits; 
   var mvl=new Array(0,100,300,0,500,0,0,0,1000,0,0,0,0,0,0,0);
   var mvl_cp=new Array(100,300,500,1000);
   var mvl_bp=new Array(0xFE,0xFD,0xFB,0xF7);

   for(col=0;col<2;col++)
   for(cp=0;cp<4;cp++)
   {
      for(b=0;b<16;b++)
      for(w=0;w<16;w++)
      {
         w_bb=0xFF;
         b_bb=0xFF;
         w_iv=0;
         b_iv=0;
         p=0;
         (col==0)?w_bb=mvl_bp[cp]:b_bb=mvl_bp[cp];
         (col==0)?w_iv=mvl_cp[cp]:b_iv=mvl_cp[cp];

         black_bits=b;
         white_bits=w;

         for(iter=1;(iter<4);iter++)
         {
            if (col==1) 
            {
               for(t=1;t<16;t=t<<1)
               {
                  if(w&t&w_bb&white_bits) // vit försvarar
                  {
                     p-=b_iv;
                     w_iv=mvl[w&t];
                     b_iv=0;
                     white_bits^=t;
                     t=16;
                  }
               }
            }

            for(t=1;t<16;t=t<<1)
            {
               if(b&t&b_bb&black_bits) // svart attackerar
               {
                  (col==0)?p-=w_iv:p+=w_iv;
                  b_iv=mvl[b&t];
                  w_iv=0;
                  black_bits^=t;
                  t=16;
               }
            }

            if (col==0)
            {
               for(t=1;t<16;t=t<<1)
               {
                  if(w&t&w_bb&white_bits) // vit försvarar
                  {
                     p+=b_iv;
                     w_iv=mvl[w&t];
                     b_iv=0;
                     white_bits^=t;
                     t=16;
                  }
               }
            }

            if (((!black_bits)||(!white_bits))&&(iter<3))
            {
               iter=3;
            }
         }
         vfm[w+(b*16)+(cp*256)+(col*1024)]=p;
      }
   }
}


Studera tilldelningen
vfm[w+(b*16)+(cp*256)+(col*1024)]=p
På motsvarande sätt hittar man sedan alla värden i denna tabell. Ledet w+b*16 är ju själva attackvärdet. Låt oss kalla detta för A. Dvs, A=w+b*16
p=vfm[A+(cp*256)+(col*1024)]
När dragen är skapade av draggeneratorn kör vi följande kod som använder översättartabellen (som är skapad enl. ovan) för att lägga till värdet om materiell vinst eller förlust. Därefter sorteras dragen m.a.p. dess tilldelade värde med funktionen bms som är en bubblesort.
   wo=pl2?0:1024;
   for (i=m_spStart;i<(m_sp-m_spStart);i++)
   {
      cp=mstv[cb[m_stFr[i]]&0xF]-1;
      if(cp>0)
      {
         attack_to=ctm[m_stTo[i]];
         if (attack_to)
         {
            if (cb[m_stTo[i]]&0xF) // pjäs attackeras
            {   
               mpoint=vfm[attack_to+cp*256+wo];
               m_moveSort[i]+=mpoint;
            }
            else
            {
               // ...
               // ...
            }
         }
      }
   }
   bms(m_spStart,m_sp-1);


footer

- Snygga visitkort på gammaldags strukturerad kartong -
move_sorting