Generering og Komprimering af Slutspil i Skak

Repræsentation af slutspil

  • Vi er interesseret i en kompakt repræsentation af slutspilsstillinger som tillader effektiv indeksering.

  • En oplagt løsning er at gruppere stillingerne efter hvilke brikker der er tilbage.
    Givet en mængde af n brikker (hvor 2 af dem må være sort og hvid konge) kan vi da repræsentere dette slutspil vha. et array med 2*64n indgange.

  • Eksempel: Slutspillet KQk (hvid konge og dronning vs sort konge).
    (Brikkerne skal være sorteret i rækkefølgen KQRBNPkqrbnp).
    Indeks = SK5K4K3K2K1K0 Q5Q4Q3Q2Q1Q0 k5k4k3k2k1k0,
    S er 0 hvis det er hvids tur og 1 hvis det er sorts tur.
    Q5Q4Q3Q2Q1Q0 er den binære repræsentation af hvid dronnings felt (for en eller anden nummerering af felterne)
    Tilsvarende for K5K4K3K2K1K0 og k5k4k3k2k1k0

  • Pladsforbrug: Hvis vi repræsenterer hver stilling med en char, vil hvert n-briks slutspil fylde 2*64n bytes. Hvis vi begrænser os til slutspil med højst 5 brikker, så har 2 KPPkp stillinger rekorderne med at være vundne hhv. tabte i 127 træk. Vi kan altså bruge nedenstående repræsentation.
  • 0 < n < = 127 repræsenterer en stilling vundet i n træk.
  • -127 <= n < = 0 repræsenterer en stilling tabt i n træk.
  • n = -128 repræsenterer en uafgjort stilling.
    •  (Med 6 brikker er der en KRNknn stilling som er vundet i 262 træk).

  • Forbedringer

  • Udnyt symmetri:
  • En stilling uden bønder og rokademulighed kan spejles både vertikalt, horisontalt og diagonalt uden at det ændrer stillingens værdi.
  • En stilling med bønder uden rokademulighed kan spejles både vertikalt uden at det ændrer stillingens værdi.
    • Vi kan udnytte ovenstående til kun at gemme de stillinger hvor en bestemt brik, lad os sige hvid konge, kun optræder indenfor a1-d1-d4 trekanten eller a1-d8 firkanten.
    Pladsforbruget er nu 2*10*64n-1 for slutspil uden bønder og 2*32*64n-1 ellers.

  • Nummerering af gyldige kongeplaceringer:
    Vi kan nummerere samtlige måder at placere de 2 konger på, hvor hvids konge er restringeret som nævnt ovenfor, og hvor afstanden mellem de 2 konger er mindst 2 kongetræk (ellers ville stillingen ikke være gyldig).
    For stillinger uden bønder kan vi ydermere restringere sort konge til a1-h1-h8 trekanden, hvis hvids konge er placeret på a1-h8 diagonalen.
    Pladsforbruget er nu 2*462*64n-2 for slutspil uden bønder og 2*1806*64n-2 ellers.

  • Restringering af bønders placering:
    Bønder kan ikke forekomme på forreste eller bagerste linje, d.v.s. de bidrager kun med en faktor 48.

  • K ens brikker:
    I et slutspil som KQQk kan vi arbitrært beslutte at den første dronning skal være placeret på et lavere feltnummer end den anden. I stedet for 642 mulige placeringer har vi altså kun 63*64/2 - altså ca. det halve. Generelt vil besparelse ved k ens brikker være ca. k!

  • Symmetriske slutspil:
    Slutspil hvor begge sider har det samme sæt brikker kaldes symmetriske. Her kan vi nøjes med at gemme stillingerne hvor det er hvids tur - har man brug for værdien af en stilling hvor det er sorts tur kan man blot bytte om på farverne af brikkerne og reflektere brædtet horisontalt.

  • Etcetera:
    Slutspilstabellerne af bl.a. Nalimov benytter sig af yderligere et par tricks. Disse bidraget dog ikke med så meget, og ved brug af ovenstående teknikker alene udgør spildpladsen kun ca. 30% for 4 briks slutspil.

  • En passant og rokade

  • I ovenstående beskrivelse tog vi ikke højde for at en passant og rokade kan være muligt i visse stillinger.
  • Problemet kan løses på 2 måder - enten ved at tilføje ekstra indekseringsrum eller ved at bruge nogle af de indekser som ellers repræsenterer ulovlige stillinger.

  • Nalimov håndterer en passant vha. ekstra indekseringsrum - formatet er så kompakt at der er ikke ulovlige stillinger nok til at repræsentere en passant stillingerne i.
  • Nalimov's tabeller ignorerer rokade, da det er ekstremt usandsynligt at nå til et slutspil og stadig have mulighed for at rokere.

  • I min repræsentation har jeg repræsenteret stillinger med en passant eller rokade som ellers ulovlige stillinger.
  • En passant:
    En mulighed for at slå en passant vedrører 2 bønder - bonden der lige flyttede 2 felter frem og bonden som slår den en passant.
    Der er 2*(1+2*6+1) = 28 mulige placeringer af disse 2 bønder. 28 af de mulige 48 placeringer for en bonde kan altså udvælges til at kode en af disse en passant muligheder. I en stilling med en passant flyttes begge 2 involverede bønder til det pågældende felt.

  • Rokade:
    Et tårn som kan indgå i en kort rokade placeres på samme felt som sin egen konge.
    Et tårn som kan indgå i en lang rokade placeres på samme felt som sin modstanderens konge.
    Problem: Med rokade er der ingen symmetri.
    Tricket med at restringere hvid konge til a1-d1-d4 trekanten eller a1-d8 firkanten kan dog stadig anvendes. Hvis kongen ikke står korrekt i forhold til at kunne rokere er det blot nødvendigt at transformere brædtet, når en stilling gendannes fra et indeks i arrayet.

    • Konstruktion af slutspilstabeller

    For at generere fx KBKP, skal de slutspil, som kan nås i et træk fra en KBKP stilling, være tilgængelige. Der er følgende tilfælde at tage højde for
  • Løberen eller springeren slås, d.v.s. KPK og KBK.
  • Bonden bliver forfremmet, d.v.s. KBKN, KBKB, KRKB og KQKB
  • Bonden bliver forfremmet samtidig med at den slår løberen.
    Dvs. KNK, KBK (allerede nævnt), KRK og KQK.
    • Der er basalt set 2 måder at generere slutspilstabellerne på.
  • Bagudrettet konstruktion/Retrograde konstruktion:
    Dette er den typisk anvendte algoritme. Den er blevet vist til en forelæsning - her skal den blot modificeres til at give afstanden til en vundet eller tabt stilling.
    Fordele/ulemper:
  • Kræver unik repræsentation af stillinger.
  • Etc. - jeg nåede ikke at gøre denne fremlæggelse færdig.
    • WTM W(-M0) => B(M1)
    BTM B(-M0) => W(M1), B(M1) => W(-M1)
    WTM W(-M1) => B(M2), W(M1) => B(-M1)
    BTM B(-M1) => W(M2), B(M2) => W(-M2)
    etc. etc.
    Symmetrisk slutspil
    WTM W(-M0) => W(M1)
    WTM W(M1) => W(-M1)
    WTM W(-M1) => W(M2)
    WTM W(M2) => W(-M2)
    etc. etc.

  • Fremadrettet konstruktion:
    Blah blah blah
    • Sammenligning - ser at den fremadrettede konstruktion tager tid proportional med den største mat-dybde.
    Endgames constructed Simple algorithm Retrograde algorithm
    All 2 and 3 men endgames 0m19.564s 0m3.572s
    All K+2 vs K endgames 64m59.912s 17m37.094s
    All K+1 vs K+1 endgames 179m5.106s 11m28.075s
    KQQQK 5m24.448s 10m30.698s
    KBBKN 832m41.147s 20m25.832s