Start | schack draggenerator
 

draggenerator



Givet en spelställning (pjäser på en bräda) och givet vems tur det är, vilka drag är möjliga för spelaren att göra?

generera möjliga drag

För att kunna göra en analys av en spelsituation behöver vi kunna räkna ut alla legala drag för båda spelare i en godtycklig situation. Denna draggenerator gör att vi kan bygga spelträd där vi med minmax och alfabeta -reducering kan analysera många framtidsscenarion i spelet.

spelplan 16x8


Som vi resonerade oss fram till på sidan om schackbrädans 0x88 -kodning så vill ha följande interna representation av spelplanen eftersom den har önskvärda binära egenskaper, så att vi lätt kan testa om en pjäs är utanför spelplanen eller inte.
Motivet är att numreringen har vissa binära egenskaper som gör det lätt testa huruvdia en pjäs befinner sig på brädan eller inte, vilket gör att vi kan skapa en väldigt snabb och kompakt draggenerator.

pjäsernas rörelser

De olika pjäsernas möjliga drag kan räknas fram genom att addera offset till positionen vi står på. Det är förstås lite mer att kontrollera, t.ex. om platsen är upptagen eller om draget ens är legalt. Men mer om det längre fram.

Hästens rörelser


För att skapa en lista av möjliga drag kan vi tänka oss att vi adderar och subtraheter lämpliga värden. T.ex. nedan för hästen, så kan vi få fram alla möjliga positioner flytta till genom att addera något av talen [-33, -31, -14, -18, 14, 31, 33, 18] till hästens utgångsläge. Titta på nedanstående bild och försäkra dig att du begriper.

Om hästen är på en sådan position att vi hamnar utanför om vi adderar [-33, -31, -14, -18, 14, 31, 33, 18] till utgångsläget, så kan vi enkelt testa det genom att ta positionen & 0x88 (dvs bit 4 eller 8 är 1 om vi är utanför.

Tornets rörelser


Tornet är en glidande pjäs. Vi får dess positioner genom att addera multipler av [-1, 1, -16, 16] till tornets utgångsläge. Hamnar pjäsen utanför? Det kan vi testa med 0x88.

Löparens rörelser


Löparen glider över spelplanen den också. Vi får dess positioner genom att addera multipler av [-17, -15, 15, 17] till löparens utgångsläge. Även här kan vi testa om pjäsen befinner sig på spelplanen med 0x88.

Drottningens rörelser


Drottningen flyttar som både tornet och löparen. Dvs, vi får dess positioner genom att addera multipler av [-1, 1, -16, 16, -17, -15, 15, 17] och vi testar om pjäsen befinner sig på spelplanen med 0x88.

Kungens rörelser


Kungen går bara ett steg i någon riktning och vi får dessa positioner genom att addera något av [-1, 1, -16, 16, -17, -15, 15, 17]. Vi testar om draget är på spelplanen med 0x88.

Bondens rörelser


Bonden är lite special och får hanteras vid sidan om. Ifall pjäsen inte har flyttat (vi har en flagga för att hålla koll på detta i pjäsens kodning), så får den flytta 2 steg fram, annars bara 1. Bonden kan också slå ut andra pjäser diagonalt, förutsatt att det står en pjäs där som kan slås ut.

Kodning


Vi kan baka ihop dessa rörelser i en och samma lista, genom att låta de första 12 positionerna i listan (vilket motsvarar pjäs) vara pekare till pjäsens rörelser längre ner i listan. Bonden är 1. Tittar vi på position 1 i listan står där 0. Det betyder att ingen information finns i listan om bonden (hanteras speciellt). Men hästens rörelser finns med start på position 32 och där hittar vi -33,-31,-14,-18,14,31,33,18,0. Serien avslutas med 0 så att vi vet att dessa offset tagit slut.

BondeHästTornLöpareDrottningKung
1248123

moff = [ 0,0,32,41,13,0,0,0,18,0,0,0,23,-1,1,-16,16,0, -17,-15,15,17,0,-1,1,-16,16,-17,-15,15,17,0, -33,-31,-14,-18,14,31,33,18,0,-1,1,-15,-16,-17,16,15,17,0 ]
Om vi bortser från bondens drag inledningsvis, så är resten av pjäserna ganska enkla hantera. Skillnaden är hästen och kungen går 1 steg medans tornet, löparen och drottningen glider över spelplanen. Vi kan enkelt testa om det är en glidande pjäs eller inte och kör då lite extra kod för att addera multipler av offset'en i moff.
pjaser = { 0x11:{"namn":"Vit Bonde", "sym":"B"}, 0x12:{"namn":"Vit Häst", "sym":"H"}, 0x13:{"namn":"Vit Kung", "sym":"K"}, 0x14:{"namn":"Vit Torn", "sym":"T"}, 0x18:{"namn":"Vit Löpare", "sym":"L"}, 0x1C:{"namn":"Vit Drottning", "sym":"D"}, 0x21:{"namn":"Svart Bonde", "sym":"b"}, 0x22:{"namn":"Svart Häst", "sym":"h"}, 0x23:{"namn":"Svart Kung", "sym":"k"}, 0x24:{"namn":"Svart Torn", "sym":"t"}, 0x28:{"namn":"Svart Löpare", "sym":"l"}, 0x2C:{"namn":"Svart Drottning", "sym":"d"} } cb = [ 0x24,0x22,0x28,0x2C,0x23,0x28,0x22,0x24,0,0,0,0,0,0,0,0, 0x21,0x21,0x21,0x00,0x21,0x21,0x00,0x21,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, 0x11,0x11,0x11,0x11,0x11,0x11,0x11,0x11,0,0,0,0,0,0,0,0, 0x14,0x12,0x18,0x1C,0x13,0x18,0x12,0x14,0,0,0,0,0,0,0,0 ] moff = [ 0,0,32,41,13,0,0,0,18,0,0,0,23,-1,1,-16,16,0, -17,-15,15,17,0,-1,1,-16,16,-17,-15,15,17,0, -33,-31,-14,-18,14,31,33,18,0,-1,1,-15,-16,-17,16,15,17,0 ] def dec2bin(d): return "{:0>6b}".format(d) def pcs(p): if(p&0x3F): return(pjaser[p&0x3F]["sym"]) else: return(":") def printBoard(): for i in range(0,128): if(not i&0x88): #print(dec2bin(cb[i]), end=" ") print(pcs(cb[i]), end=" ") else: print("{: >3d}".format(i-8), end=" ") if(not (i+1)%16): print() def moveList(fpos,pl): # från position + spelare mLst=[] # lista med drag P = cb[fpos] # pjäs på pos fpos glidande = (P&0x02 != 2) # glidande pjäs? poff = moff[P&0x0F] # pekare till dragoffset while(t :=moff[poff]): # sålänge det finns offset poff=poff+1 m = fpos + t # räkna ut vart pjäs hamnar if(m&0x88): continue # hamnade utanför brädan if(cb[m] and (pl&cb[m])==pl): continue # egen pjäs på positionen mLst.append({ # OK! lägg till movelistan "pjas":P&0x3F, "fran":fpos, "till":m, "glidande":glidande }) if(not glidande): # ej glidande pjäs, avbryt continue g = 2 # glidande, så räkna på draf while(g<9): # max 8 drag m = fpos + t*g # räkna ut vart pjäs hamnar if(m&0x88): break # hamnade utanför brädan if(cb[m] and (pl&cb[m])==pl): break # egen pjäs blockerar mLst.append({ # OK! lägg till movelistan "pjas":P&0x3F, "fran":fpos, "till":m, "glidande":glidande }) if(cb[m] and (pl&cb[m])!=pl): break # slog ut fiendes pjäs (bra!) g = g + 1 # glid vidare 1 position return(mLst) def allMoves(pl): mLst=[] for m in range (0,128): if(not m&0x88): if(cb[m] and (0x30&cb[m])==pl): mLst.extend(moveList(m,pl)) return(mLst) def printMveLst(pl): lst = allMoves(pl) for l in lst: print("{0} från {1} till {2} ".format( pjaser[l["pjas"]]["namn"],l["fran"],l["till"])) printBoard() printMveLst(0x20) # egen pjas motspelare pjas
Ovan kodsnurra moveList blir väldigt kompakt och effektiv. Tyvärr återstår alla undantag att hantera, t.ex. bondens rörelser. Bonden har möjlighet att flytta 2 steg första gången, annars 1 steg. Dessutom slår bonden diagonalt. Vi nöjer oss med det tills vidare. Vi kan använda bit 7 för att testa om bonden rört sig något i spelet. Om inte - då får bonden flytta 2 steg. Vi testar också om det finns en motsatt spelare att slå diagonalt. Isåfall lägger vi till den positionen också. Vi måste också hantera svart och vit omvänt, dvs vita bönder flyttar "bakåt" matematiskt och svarta bönder flyttar "fram" matematiskt.
pjaser = { 0x11:{"namn":"Vit Bonde", "sym":"B"}, 0x12:{"namn":"Vit Häst", "sym":"H"}, 0x13:{"namn":"Vit Kung", "sym":"K"}, 0x14:{"namn":"Vit Torn", "sym":"T"}, 0x18:{"namn":"Vit Löpare", "sym":"L"}, 0x1C:{"namn":"Vit Drottning", "sym":"D"}, 0x21:{"namn":"Svart Bonde", "sym":"b"}, 0x22:{"namn":"Svart Häst", "sym":"h"}, 0x23:{"namn":"Svart Kung", "sym":"k"}, 0x24:{"namn":"Svart Torn", "sym":"t"}, 0x28:{"namn":"Svart Löpare", "sym":"l"}, 0x2C:{"namn":"Svart Drottning", "sym":"d"} } cb = [ 0x24,0x22,0x28,0x2C,0x23,0x28,0x22,0x24,0,0,0,0,0,0,0,0, 0x21,0x21,0x21,0x00,0x21,0x21,0x00,0x21,0,0,0,0,0,0,0,0, 0x00,0x00,0x00,0x11,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, 0x11,0x11,0x11,0x11,0x11,0x11,0x11,0x11,0,0,0,0,0,0,0,0, 0x14,0x12,0x18,0x1C,0x13,0x18,0x12,0x14,0,0,0,0,0,0,0,0 ] moff = [ 0,0,32,41,13,0,0,0,18,0,0,0,23,-1,1,-16,16,0, -17,-15,15,17,0,-1,1,-16,16,-17,-15,15,17,0, -33,-31,-14,-18,14,31,33,18,0,-1,1,-15,-16,-17,16,15,17,0 ] def dec2bin(d): return "{:0>6b}".format(d) def pcs(p): if(p&0x3F): return(pjaser[p&0x3F]["sym"]) else: return(":") def printBoard(): for i in range(0,128): if(not i&0x88): #print(dec2bin(cb[i]), end=" ") print(pcs(cb[i]), end=" ") else: print("{: >3d}".format(i-8), end=" ") if(not (i+1)%16): print() def moveList(fpos,pl): # från position + spelare mLst=[] # lista med drag P = cb[fpos] # pjäs på pos fpos if(P&0x3F==0x11): # vit bonde if(not cb[fpos-16]): # ledigt framför ?? mLst.append({ # Ja, lägg till movelistan "pjas":P&0x3F, "fran":fpos, "till":fpos-16, "glidande":False }) if(not P&0x40 and not cb[fpos-32]): # ej flyttad mLst.append({ # då är 2 steg "pjas":P&0x3F, # möjligt "fran":fpos, "till":fpos-32, "glidande":False }) m = fpos-15 if(cb[m] and 0x30&cb[m]!=pl and not m&0x88): mLst.append({ # slå snett möjligt "pjas":P&0x3F, "fran":fpos, "till":m, "glidande":False }) m = fpos-17 if(cb[m] and 0x30&cb[m]!=pl and not m&0x88): mLst.append({ # slå snett möjligt "pjas":P&0x3F, "fran":fpos, "till":m, "glidande":False }) return(mLst) if(P&0x3F==0x21): # svart bonde if(not cb[fpos+16]): # ledigt framför ?? mLst.append({ # Ja, lägg till movelistan "pjas":P&0x3F, "fran":fpos, "till":fpos+16, "glidande":False }) if(not P&0x40 and not cb[fpos+32]): # ej flyttad mLst.append({ # då är 2 steg "pjas":P&0x3F, # möjligt "fran":fpos, "till":fpos+32, "glidande":False }) m = fpos+15 if(cb[m] and 0x30&cb[m]!=pl and not m&0x88): mLst.append({ # slå snett möjligt "pjas":P&0x3F, "fran":fpos, "till":m, "glidande":False }) m = fpos+17 if(cb[m] and 0x30&cb[m]!=pl and not m&0x88): mLst.append({ # slå snett möjligt "pjas":P&0x3F, "fran":fpos, "till":m, "glidande":False }) return(mLst) glidande = (P&0x02 != 2) # glidande pjäs? poff = moff[P&0x0F] # pekare till dragoffset while(t :=moff[poff]): # sålänge det finns offset poff=poff+1 m = fpos + t # räkna ut vart pjäs hamnar if(m&0x88): continue # hamnade utanför brädan if(cb[m] and (pl&cb[m])==pl): continue # egen pjäs på positionen mLst.append({ # OK! lägg till movelistan "pjas":P&0x3F, "fran":fpos, "till":m, "glidande":glidande }) if(not glidande): # ej glidande pjäs, avbryt continue g = 2 # glidande, så räkna på draf while(g<9): # max 8 drag m = fpos + t*g # räkna ut vart pjäs hamnar if(m&0x88): break # hamnade utanför brädan if(cb[m] and (pl&cb[m])==pl): break # egen pjäs blockerar mLst.append({ # OK! lägg till movelistan "pjas":P&0x3F, "fran":fpos, "till":m, "glidande":glidande }) if(cb[m] and (pl&cb[m])!=pl): break # slog ut fiendes pjäs (bra!) g = g + 1 # glid vidare 1 position return(mLst) def allMoves(pl): mLst=[] for m in range (0,128): if(not m&0x88): if(cb[m] and (0x30&cb[m])==pl): mLst.extend(moveList(m,pl)) return(mLst) def printMveLst(pl): lst = allMoves(pl) for l in lst: print("{0} från {1} till {2} ".format( pjaser[l["pjas"]]["namn"],l["fran"],l["till"])) printBoard() printMveLst(0x20) # egen pjas motspelare pjas
♙ ♖ ♔ ♗ ♘ ♖
19.905090332031 ms