Draggenerator
Allmänt
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.

0x88
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.

Exempel
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.
var torn=new Array(-1,1,-16,16,0);
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.

Generalisering
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.
BondeTornHästLöpareDrottningKung
Bonde
1
Torn
4
Häst
2
Löpare
8
Drottning
12
Kung
3


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.

 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

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++;
  }
}


Undantag
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.

Rockad
För att få göra rockad måste följande villkor vara uppfyllda. 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).

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



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

Skapar spelplanen ...

           



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







Noter
1 Wikipedia om 2-komplement

footer

- Snygga visitkort på gammaldags strukturerad kartong -
move_generator_0x88