Spela schack | Om dataschack | Koda spelbräda | Öppningsspel | Evalueringsfunktion | Draggenerator | Minimax & Alfabeta-reducering | Dragsortering | Slutspel | Schackregler | Javascript | Länkar/referenser

header
Spelbräda (och pjäser)
Om kodningen
Detta är tredje versionen av spelbrädans kodning. Tydligen måste man ibland göra en del misstag för att komma till vissa insikter, men nu har jag fått ordentlig kläm på exakt hur jag ska tänka.

Siffror här nedan som är på formen 0x10 eller 0x2C är hexadecimala tal. Jag har valt denna skrivform eftersom talen här är valda för att de har vissa binära egenskaper. Det hexadecimala skrivsättet är enklare att överföra till binär form än det decimala.

0x88
Själv spelbrädan har jag nu gjort efter 0x88 som förebild. Det innebär att jag använder en matris på 16x8 rutor, detta för att placera pjäserna på positioner med vissa binära egenskaper.
var cb0x88 = new Array(
  0x12,0x13,0x14,0x16,0x15,0x14,0x13,0x12,0,0,0,0,0,0,0,0,
  0x11,0x11,0x11,0x11,0x11,0x11,0x11,0x11,0,0,0,0,0,0,0,0,
  0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0,0,0,0,0,0,0,0,
  0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0,0,0,0,0,0,0,0,
  0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0,0,0,0,0,0,0,0,
  0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0,0,0,0,0,0,0,0,
  0x01,0x01,0x01,0x01,0x01,0x01,0x01,0x01,0,0,0,0,0,0,0,0,
  0x02,0x03,0x04,0x06,0x05,0x04,0x03,0x02,0,0,0,0,0,0,0,0);
Ovanstående matris betyder att schackbrädan ser ut som till höger. Själva poängen med att göra detta är som jag nämde att ge spelhalvan av denna konstruktion positioner med vissa binära egenskaper. Dessa binära egenskaper gör att vi kan skilja på nummer som befinner sig på och utanför schackbrädan genom en enkel logisk bitvis jämförelse. Att vi kan göra denna enkla jämförelse betyder senare att vi kan göra en mycket snabb draggenerator.

Studera siffrorna här till höger och titta sedan på den tabell med binära tal du ser nedan. Jag har klippt in binära tal för några negativa nummer samt nummer utanför schackbrädans positioner.

Titta riktigt noga på den första 1:an eller 0:an i varje gruppering.

  XYYY XYYY

Gemensamt med den inringade schackbrädan är att varje första bit i grupperingarna båda är noll. Placeringar utanför schackbrädan har det gemensamt att där är första biten i dessa grupperingar 1. Notera hur de negativa binära talen ser ut eftersom datorer använder 2-komplement. Denna systematiska skillnad kan vi enkelt identifiera genom att ta en position på eller utanför spelbrädan och göra en logisk AND med 0x88 (binärt 1000 1000).

<% Function Dec2Bin(dec) Dim bin, temp, d bin = "" d=dec if d<0 then d =d+128 end if do while (d > 0) if (d mod 2) = 0 then temp = "0" else temp = "1" d = d -1 end if d = d / 2 bin = temp + bin loop do while len(bin)<7 bin="0"+bin loop if dec<0 Then bin="1"+bin else if len(bin)<8 then bin="0"+bin end if end if Dec2Bin= Left(bin,4) & " " & Right(bin,4) Dec2Bin= "" & Left(Dec2Bin,1) & "" & Mid(Dec2Bin,2,4) & "" & Mid(Dec2Bin,6,1) & "" & Right(Dec2Bin,3) End Function Dim hxchr, binchr for i=0 to 31 binchr=Dec2Bin(i) 'hxchr=Mid("0123456789ABCDEF",i,1) %> <% next %>
<%Response.Write -i-1%>  
<%Response.Write Dec2Bin(-i-1)%>    
<%Response.Write i%>  
<%Response.Write Dec2Bin(i)%>    
<%Response.Write i+32%>  
<%Response.Write Dec2Bin(i+32)%>  
<%Response.Write i+64%>  
<%Response.Write Dec2Bin(i+64)%>  
<%Response.Write i+96%>  
<%Response.Write Dec2Bin(i+96)%>  
<%Response.Write i+128%>  
<%Response.Write Dec2Bin(i+128)%>  


Det betyder alltså att om vi har en postition fpos, då kan vi alltså enkelt testa om denna position finns på schackbrädan med följande enkla och vackra logik. Vi filtrerar enkelt bort alla drag som inte hamnar på schackbrädan. Om du fortfarande inte kopplat varför metoden kallas 0x88 kanske börjar gå upp ett ljus nu.
if (!(fpos&0x88))
{
....
}
Denna enkla logik kan vi arbeta vidare på. Vi kan göra en snurra som adderar eller subtraherar tal för att få alla schackdrag och vi kan enkelt utesluta det drag som hamnar utanför spelplanen.

Spelpjäserna
Om man stångas ett tag med draggenereringen kan man identifiera den logik som draggeneratorn behöver för att fungera.
Inspirerad av de enkla lösningar 0x88:an ger när det gäller att testa om drag är innanför eller utanför kan vi skapa samma sköna logik för andra frågor som dyker upp i draggeneratorn.

Efter lite funderande kan man t.ex. komma fram till att följande pjäskodning är väldigt effektiv, betraktat som ett 8-bitars tal. Detaljen som gör skillnad är hur jag kodar pjäsens färg.



Jag har valt att koda pjäserna på följande sätt.

BondeTornHästLöpareDrottningKung
Bonde
0x11 / 0x21
Torn
0x14 / 0x24
Häst
0x12 / 0x22
Löpare
0x18 / 0x28
Drottning
0x1C / 0x2C
Kung
0x13 / 0x23

Varför dessa värde? Varför inte bara ge dem index från 1-6 för vit och t.ex. 11-16 för svart? Poängen med att koda pjäserna på det ena eller andra sättet är att vissa sätt att koda gör det möjligt att göra enkla tester på schackbrädan. Sådana tester vi vill göra inkluderar t.ex.

 Vit      (binärt)Svart (binärt)
Bonde0x110001 0001   0x210010 0001
Häst0x120001 00100x220010 0010
Löpare0x180001 10000x280010 1000
Torn0x140001 01000x240010 0100
Drottning  0x1C0001 11000x2C0010 1100
Kung0x130001 00110x230010 0011

1 Speciellt denna fråga är intressant t.ex. när vi flyttar en glidande pjäs över schackbrädan. Säg att vi flyttar ett svart torn över spelbrädan. Villkoret för att kunna flytta tornet till en ruta är att rutan antingen är tom eller att där står en vit pjäs (som vi då slår ut). Men vi kan inte flytta utanför spelbrädan och vi kan inte köra över en pjäs av vår egen färg.

Kodningen av vad som är vitt och svart ger oss en enkel skön logik för detta. För att t.ex. testa nyss nämda ser koden ut så här ...
if (top&0x88) break;
if (top&pl;) break;

      ...draget är okej...

Det är nästan så att man undrar vart koden tagit vägen, så kompakt blir det. Tillsammans med den enkla logiken som 0x88 -brädan ger borde vi krattat manegen för en snygg kompakt och snabb kod. Läs mer om detta under draggenereringen.

N -biten
N -biten använder vi för att avgöra om en pjäs har flyttats eller inte. Så fort vi flyttar en pjäs första gången sätter vi denna bit till noll. Därefter förblir den noll. Informationen används bl.a. när vi skall avgöra om rockad är legalt eller inte, då vi behöver veta om kungen eller tornen har flyttats någon gång.