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

Dragenerator för schack kommer beskrivas bättre på python-rummet framöver då jag går igenom allt detta och skriver om koden i python. Det kommer bli lättare att begripa, lättare testa koden själv osv.

Denna funktion implementerar själva reglerna i schacket. I en given situation vill man t.ex. veta alla legala drag vit spelare kan göra. Vi vill kunna göra ett drag i denna lista av drag och sedan anlysera läget på spelplanen med evalueringsfunktionen. Därefter skall detta drag göras ogjort för att kunna prova ett annat drag.

Draggeneratorn skall också göra en del förarbete så att sökfunktionerna kan arbeta så optimalt som möjligt. Det viktigaste här är att sortera draglistan så att dramatiska drag testas före odramatiska drag.

För att denna anlys skall vara möjlig av dragsorteringen producerar draggeneratorn positionella och vektoriella attackvärden.

Lite mer exakt hur detta görs och varför står beskrivet under dragsortering. Här nedan beskriver jag bara hur själva draggeneratorn fungerar.

Jag beskrev under avsnittet med spelbrädan hur konceptet med 0x88 fungerar och varför spelbrädan ser ut som den gör. Nu är det dags att använda dessa egenskaper skarpt.

Algoritmen för draggeneratorn är ganska enkel. Det finns inget magiskt här utom möjligtvis tricket att få den mycket snabb. Tittar man på spelbrädan så kan man identifiera den enkla matematik som ligger bakom rutornas inbördes relation med avseende på de olika spelpjäserna.



Ett uppenbart sätt att koda en draggenerator är att göra snurror som tar fram de olika spelpjäsernas drag. (Föresten, finns det något annat sätt? En komplex datastruktur? - hör av dig om du har ideer)

Man kan t.ex. skapa en matris som nedan. Studera siffrorna till höger och försäkra dig att du förstår varför dessa värden är följande. Vänster, höger, upp och ner. Dvs tornets rörelser.
Koden för att på position fpos lägga till tornets alla drag på stacken blir då

           ix=0;
           while (ox=torn[ix++])
           {
              ox+=fpos;
              if (!(ox&0x88))
              {
                 top=cb[ox];
                 if (!(top&pl;))
                 {
                    m_stFr[m_sp]=fpos;
                    m_stTo[m_sp]=ox;
                    m_sp++;
                 }
              }
           }

Lägg märke till hur löjligt kompakt denna kod blir och den är fullt läsbar och begriplig. Vi står på position fpos när vi går in i koden. Vi lägger till ett drag som tornet kan göra. Om detta drag ligger utanför schackbrädan provar vi nästa drag om det är möjligt. Ligger draget innanför schackbrädan tittar vi vad det står för pjäs på den ruta dit vi skall flytta. Om det inte står en pjäs av vår egen färg eller rutan är tom (om vi är svart skall rutan alltså antingen vara tom eller innehålla en vit pjäs, som då slår ut) då är draget preliminärt legalt och vi lägger det på stacken. Ett drag som draggeneratorn betraktar som legalt kan vara illegalt av andra orsaker som sedan sökalgoritmen upptäcker, t.ex. att kungen sätts i schack, men jag lämnar den detaljen tills vidare.

Vi kan bunta ihop några pjäser och använda samma snurra. Det är löpare, tornet, drottningen, hästen och kungen. Matrisen moff lagrar alla drag för dessa 5 pjäser ligger. Den första raden (1) innehåller pekare till övriga rader. Första radens pekare indexeras dessutom med pjäsens värde. Varje rad avslutas med noll så att vi vet när riktningarna för en pjäs slutar.

var moff = new Array(0,0,32,41,13,0,0,0,18,0,0,0,23, (1)
                    -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);

Pjäsernas värde på decimal form nedan. Notera detta värde och studera pekarens placering i matrisen (1) här ovan. Observera att bonden inte räknas ut med denna kod.


Koden som använder moff och plockar fram alla legala drag för häst, kung, torn, löpare och drottning ser då ut som nedan. Koden ger också drag som eliminerar pjäser poäng enligt de sorteringsprinciper som gäller (se längre ner) samt ger extra poäng för senast utslagna pjäs.

Alla nämnda pjäser fungerar likadant så när som på en liten detalj. Hästen och kungen går ett steg medans övriga glider över spelplanen fram till spelplanens vägg. Snurran som tar oss fram till en vägg är (1) och koden som hoppar ut redan vid snurrans första varv (2). För att förstå vad (2) gör studera den kodning jag gav pjäserna och notera att denna logiska operation identifierar just hästen och kungen. Jag testar bit 2 (2) vilket träffar kung och häst och om sant så hoppar vi ur snurran - annars förutsätts pjäsen röra sig mot en vägg.

if (fromp&0x0E)
{
  jx=moff[fromp&0x0F];
  while (t=moff[jx])
  {
    ix=1;
    while (ix<8) (1)
    {
      ox=fpos+ix*t;
      if (ox&0x88) break;
      top=cb[ox];
      if (top&pl;) break;
      m_moveSort[m_sp]=0;
      m_stFr[m_sp]=fpos;
      m_stTo[m_sp]=ox;
      if (top&pl;_inv)
      {
        ms=((lstCap==ox)?6000:2000+sc*(mv[cb[ox]]-mv[cb[fpos]]));
        m_moveSort[m_sp]=ms;
        bms(m_spStart,m_sp);
        break;
      }
      m_sp++;
      if (fromp&0x02) break; (2)
      ix++;
    }
    jx++;
  }
}

Det finns pjäser i schack som glider över spelplanen och det finns pjäser som hoppar 1 steg. Sen finns några drag som står helt vid sidan som behöver hanteras separat på något sätt.

För att få göra rockad måste följande villkor vara uppfyllda.

• Det måste vara fritt mellan kungen och tornet
• Kungen och tornet som får inte ha flyttats
• Kungen och tornet får inte passera någon hotad ruta
• Kungen får inte vara i schack

Eftersom draggeneratorn producerar all nödvändig information, en händelse som ser ut som en tanke, om hotade rutor och det dessutom råkar finnas en kontroll-bit som markerar om en pjäs är flyttad är det bara att testa villkoren. Det blir ganska ful och "klumpig" kod men den fungerar tills vidare.

if (fromp==0x03) // kung, rockad
{
  if (!(ct[fpos]&pl;_inv))  // kung ej schackad
  {
    if ((!(ct[fpos-2]&pl;_inv))&&(!(ct[fpos-1]&pl;_inv))&&
    (!((cb[fpos-2]&0x3F)|(cb[fpos-1]&0x3F)))&&
    (cb[fpos-3]==(0x44|pl))&&(cb[fpos]==(0x43|pl)))
    {
      m_moveSort[m_sp]=500;
      m_stFr[m_sp]=fpos;
      m_stTo[m_sp]=fpos-2;
      bms(m_spStart,m_sp);
      m_sp++;
    }
    if ((!(ct[fpos+1]&pl;_inv))&&(!(ct[fpos+2]&pl;_inv))&&
    (!(ct[fpos+3]&pl;_inv))&&
    (!((cb[fpos+1]&0x3F)|(cb[fpos+2]&0x3F)|(cb[fpos+3]&0x3F)))&&
    (cb[fpos+4]==(0x44|pl))&&(cb[fpos]==(0x43|pl)))
    {
      m_moveSort[m_sp]=500;
      m_stFr[m_sp]=fpos;
      m_stTo[m_sp]=fpos+2;
      bms(m_spStart,m_sp);
      m_sp++;
    }
  }
}

Notera också att jag ger rockad-draget 500 poäng. Detta så att det skall sorteras in på rätt position enligt sorteringsprinciperna (läs mer under sortering).

Med bonden har vi att brottas med ett antal irregulariteter, det är.

• 2-stegsflytt. Första draget får bonden flytta 2 steg fram - annars bara ett steg fram. Bonden slår snett.
• En passant. Bonde som gjort 2-stegs flytt kan elimineras följande drag med en passant.
• Bonde som avancerar till andra sidan spelbrädan avancerar till valfri pjäs, i praktiken till drottning.

Om du klickar på brädan här intill och flyttar på pjäserna kan du laborera med draggeneratorn.



Till höger om bräden hittar du alla legala drag för respektive färg enl. svensk notation.







Noter
¹ Wikipedia om 2-komplement