• Strona główna
  • Debiuty szachowe
  • Miniatury szachowe
  • ChessExplorer



       

  • SZACHY
    ilość wariantów

    Czy białe, przy najlepszej grze, tak swojej, jak i przeciwnika, wygrają czy też uzyskają tylko remis?
    A jeśli mają możliwość wygrania, to jak powinny grać?

        Aby uzyskać odpowiedzi na te pytania wystarczy napisać prosty program, analizujący wszystkie możliwe warianty (tak działają Explorer i ChessExplorer) , wprowadzić początkową pozycję na szachownicy, zadać poszukiwanie mata np. w 50 ruchach i ... poczekać odpowiednio długo.

    Czas oczekiwania na wynik byłby rzeczywiście dosyć długi, bo liczba wariantów do przeanalizowania, jak się zaraz okaże, jest ogromna.
    Można w pewnym stopniu przyśpieszyć analizę przez zastosowanie szybszych procesorów czy systemów wieloprocesorowych (np. badania rozproszone na wielu komputerach, jak w projekcie SETI@Home) i oczywiście poprzez optymalizację kodu programu.
    Tu mała dygresja
    Pierwszy z dwóch wymienionych programów (Explorer) napisany został w TurboPascalu i przy przeciętnym sprzęcie analizuje ok. 10 000 posunięć w ciągu sekundy. W zamierzchłych czasach 8-bitowych Atari (starsze osoby, po 20-tce, pamiętają ten komputer składający się z klawiatury) program oparty na tym samym algorytmie sporządzony został bezpośrednio w języku maszynowym procesora 6502. Kod programu, łącznie z boot-sectorem na dyskietce, zajmował tylko 2,5 kB (czy są teraz takie programy?) i przy zegarze 1,77 MHz (!) działał niewiele wolniej, niż ten obecny.
    Drugi z programów (ChessExplorer), napisany w C++ i assemblerze (podstawowe procedury), jest znacznie szybszy, gdyż kod programu został zoptymalizowany pod kątem pełnego wykorzystania możliwości procesorów z rodziny Pentium.
    Wszystko to niewiele nam jednak da, bo przy przyśpieszeniu obliczeń nawet miliard razy, nasze wnuki nie doczekałyby się wciąż rozwiązania.
    Przypuszczalnie realna, jak mi się wydaje, możliwość rozwiązania problemu to skonstruowanie specjalnego procesora lub układu procesorów, zaprojektowanych specjalnie w tym jednym, jedynym celu (ale kto na to pójdzie?).

    Spróbujmy więc oszacować liczbę możliwych wariantów w partii szachowej.
    Przy rozpoczęciu partii białe mają 20 możliwości, w następnym posunięciu czarne posiadają także 20 możliwości ruchu, czyli w dwóch pierwszych pojedyńczych posunięciach jest 400 różnych wariantów gry.
    Ilość możliwych kontynuacji szybko wzrasta wraz z kolejnymi ruchami i, jak łatwo ( :-) ) można stwierdzić, wynosi:
    po 3 posunięciach -
    8.902
    po 4 posunięciach -
    197.281
    po 5 posunięciach -
    4.865.609
    po 6 posunięciach -
    119.060.324
    po 7 posunięciach -
    3.195.901.860
    po 8 posunięciach -
    91.768.468.861
    Z tej ostatniej liczby 8.102.108.221 to warianty zaczynające się od posunięcia e2 - e4, a tylko 2.863.411.653 - od posunięcia a2 - a3.
    Nie polecam dokonywania tych obliczeń "na piechotę". Dużo łatwiej napisać programik, zliczający poszczególne warianty (lub skorzystać z ChessExplorer'a).
    Analizując te pierwsze liczby można zauważyć, że białe są tutaj już nieco uprzywilejowane. W trzecim posunięciu (drugim białych) jest średnio 22,26 możliwych odpowiedzi na ruch przeciwnika (8.902 : 400), w czwartym (czarne) - 22,16, w piątym (białe) - 24,66, w szóstym (czarne) - 24,47, w siódmym (białe) - 26,85 i w ósmym (carne) - 26,60.
    W miarę rozwinięcia partii średnia liczba możliwych ruchów wzrasta w dalszym ciągu, lecz w sposób zróżnicowany, w zależności od zastosowanego debiutu.

    Dla zaspokojenia ciekawości zafascynowanych magią liczb i teorią debiutów szachowych kilka danych dotyczących popularnych otwarć:

    Partia hiszpańska
    1. e2 - e4, e7 - e5
    2. Sf1 - f3, Sb8 -c6
    3. Gf1 - b5, a7 - a6


    W tej pozycji ilość dalszych możliwych kontynuacji gry wynosi:
      w 1 nast. posunięciu (białe)-
    32 (x32,00)
      w 2 nast. posunięciach (cz.)-
    1.019 (x31,84)
      w 3 nast. posunieciach (b.)-
    32.647 (x32,04)
      w 4 nast. posunięciach (cz.)-
    1.013.312 (x31,04)
      w 5 nast. posunięciach (b.)-
    32.766.760 (x32,34)
      w 6 nast. posunięciach (cz.)-
    1.031.427.145 (x32,22)


    Gambit królewski
    1. e2 - e4, e7 - e5
    2. f2 - f4, d7 - d5
    3. e x d5, e5 - e4


    Ilość dalszych możliwych kontynuacji:
      w 1 nast. posunięciu (białe)-
    30 (x30,00)
      w 2 nast. posunięciach (cz.)-
    1.098 (x36,60)
      w 3 nast. posunieciach (b.)-
    32.755 (x29,83)
      w 4 nast. posunięciach (cz.)-
    1.196.835 (x36,54)
      w 5 nast. posunięciach (b.)-
    36.653.001 (x30,62)
      w 6 nast. posunięciach (cz.)-
    1.422.520.851 (x37,36)


    Obrona królewsko-indyjska
    1. d2 - d4, Sg8 - f6
    2. c2 - c4, g7 - g6
    3. Sb1 - c3, Gf8 - g7


    Ilość dalszych możliwych kontynuacji:
      w 1 nast. posunięciu (białe)-
    33 (x33,00)
      w 2 nast. posunięciach (cz.)-
    849 (x25,73)
      w 3 nast. posunieciach (b.)-
    28.896 (x34,04)
      w 4 nast. posunięciach (cz.)-
    779.565 (x26,98)
      w 5 nast. posunięciach (b.)-
    27.200.124 (x34,89)
      w 6 nast. posunięciach (cz.)-
    824.153.606 (x28,21)


    Obrona Nimzowitscha
    1. d2 - d4, Sg8 - f6
    2. c2 - c4, e7 - e6
    3. Sb1 - c3, Gf8 - b4


    Ilość dalszych możliwych kontynuacji:
      w 1 nast. posunięciu (białe)-
    27 (x27,00)
      w 2 nast. posunięciach (cz.)-
    883 (x32,70)
      w 3 nast. posunieciach (b.)-
    25.596 (x28,99)
      w 4 nast. posunięciach (cz.)-
    831.371 (x32,48)
      w 5 nast. posunięciach (b.)-
    25.788627 (x31,02)
      w 6 nast. posunięciach (cz.)-
    894.253.379 (x32,58)

    Widoczne tu jest np., że w obronie królewsko-indyjskiej czarne mają mniejsze od białych możliwości manewru, a w gambicie królewskim - przeciwnie. W tym ostatnim ostrym debiucie, liczba możliwych kombinacji wzrasta szybciej, niż średnio w innych wariantach.

    W grze środkowej ilość możliwych kontynuacji waha się, co zrozumiałe, w zależności od pozycji, w zakresie od ok. 20 do ok. 50 możliwych odpowiedzi w każdym posunięciu.

    W pozycji na diagramie, do której doszło po 40 ruchach w partii Petrosjan - Larsen (1966r.), ilość dalszych możliwych kontynuacji wynosi:
      w 1 nast. posunięciu (białe)-
    23 (x23,00)
      w 2 nast. posunięciach (cz.)-
    715 (x31,09)
      w 3 nast. posunieciach (b.)-
    15.301 (x21,40)
      w 4 nast. posunięciach (cz.)-
    486.272 (x31,78)
      w 5 nast. posunięciach (b.)-
    10.628.124 (x21,86)
      w 6 nast. posunięciach (cz.)-
    358.733.276 (x31,61)


    W partii Capablanca - Marshall z 1918r. po 15 posunięciach:
    1. e2-e4, e7-e5 2. Sg1-f3, Sb8-c6 3. Gf1-b5, a7-a6 4. Gb5-a4, Sg8-f6 5. 0-0, Gf8-e7 6. Wf1-e1, b7-b5 7. Ga4-b3, 0-0 8. c2-c3, d7-d5 9. e4:d5, Sf6:d5 10. Sf3:e5, Sc6:e5 11. We1:e5, Sd5-f6 12. We5-e1, Ge7-d6 13. h2-h3, Sf6-g4 14. Hd1-f3, Hd8-h4 15. d2-d4, Sg4:f2
    doszło do pozycji przedstawionej na diagramie.

    Ilość najbliższych możliwych kontynuacji wynosi tutaj:

      w 1 nast. posunięciu (białe)-
    47 (x47,00)
      w 2 nast. posunięciach (cz.)-
    2.000 (x42,55)
      w 3 nast. posunieciach (b.)-
    85.545 (x42,77)
      w 4 nast. posunięciach (cz.)-
    3.638.773 (x42,54)
      w 5 nast. posunięciach (b.)-
    150.336.360 (x41,32)
      w 6 nast. posunięciach (cz.)-
    6.723.982.987 (x42,75)

    Partię tę, po precyzyjnej grze, wygrał późniejszy mistrz świata Jose Raul Capablanca, ale zastosowany tu debiut z poświęceniem piona na e5 i uzyskaniem przez czarne dużych możliwości ataku, wszedł do teorii szachowej pod nazwą kontrataku Marshalla.

    W końcówkach, z uwagi na mniejszą ilość bierek, liczba możliwych kontynuacji jest oczywiście z reguły mniejsza i w dużym stopniu zróżnicowana, w zalezności od rodzaju bierek pozostałych na szachownicy.


         Po tych wspominkach z partii rozgrywanych przez czołowych szachistów można spróbować oszacować, ile wariantów musiałby przeanalizować komputer, aby uzyskać odpowiedź na postawione na początku pytanie.

    Po odpowiednim wymnożeniu tych liczb otrzymujemy:

    ilość wariantów = 1011 . 1078 . 1025 . 1020 = 10134

    Jeśli nasz program będzie analizował 1.000.000 wariantów w ciągu sekundy, to na przerobienie całości będzie potrzebował ok. 10120 lat.
    Jest to liczba większa, niż szacowana ilość atomów w obserwowalnym wszechświecie i nawet przyśpieszenie obliczeń bilion razy (1012) niewiele zmieni, bo otrzymamy wtedy ciągle wysoki rząd wielkości: 10108 lat.

    Mimo wszystko, może to i lepiej, bo gdybyśmy znali odpowiedzi na postawione na wstępie pytania, co robiliby nasi wspaniali arcymistrzowie, a sens straciłaby m.in. cała, pracowicie latami tworzona i rozbudowywana, teoria debiutów szachowych.


    * * *

         Pewna część ze wszystkich możliwych wariantów gry w danej pozycji to takie, które sprowadzają się do prostego powtarzania posunięć przez obydwie strony (i ciągłego powtarzania pozycji). W programie komputerowym możemy łatwo wyeliminować takie "zapętlenia się". Ale do identycznych pozycji na szachownicy można dojść także poprzez odmienną kolejność tych samych posunięć. Przy określonych ośmiu posunięciach (czterech białych i czterech czarnych) możemy mieć 576 różnych sekwencji ruchów (tych samych posunięć, lecz w różnej kolejności) prowadzących do tej samej pozycji.
    Grający program szachowy przy rozgrywaniu partii tworzy bazę przeanalizowanych już pozycji wraz z ich oceną. Zmniejsza to ilość rozpatrywanych posunięć w ciągu sekundy (konieczność przeszukiwania tej bazy i jej aktualizowania) ale eliminuje powtórne analizowanie tej samej pozycji (całej gałęzi ruchów wynikających z tej pozycji).

    Ilość możliwych przebiegów partii szachowej określiliśmy szacunkowo na 10134.
    Jaka jest ilość możliwych do uzyskania pozycji na szachownicy?
    Jest to zadanie ściśle zdefiniowane, ale nie jest łatwe do rozwiązania. Możemy próbować podejść do tego w poniższy sposób.

    Dla każdej z możliwych ilości bierek na szachownicy (od 2 do 32) obliczamy liczbę możliwych różnych zestawów bierek składających się na tę łączną ilość.
    Dla każdej ilości bierek wybieramy w miarę reprezentatywny zestaw bierek i obliczamy na ile sposobów zestaw ten można rozmieścić na szachownicy. Staramy się uwzględnić tu tylko, co nie zawsze jest proste, pozycje możliwe do uzyskania.
    Po wymnożeniu odpowiednich wielkości (dla każdej z ilości bierek, od 2 do 32) i zsumowaniu wyników otrzymamy końcowy rezultat.

    Przykładowo dla 2 bierek możliwy jest tylko jeden zestaw bierek: 2 króle.
    Dla 3 bierek istnieje 10 różnych zestawów: 2 króle plus jedna z pozostałych białych lub czarnych bierek.
    Dla 4 bierek mamy 35 zestawów (mogą tu być też 2 hetmany tego samego koloru).
    Dla 16 bierek otrzymamy ok. 809 tysięcy możliwych zestawów, a dla 24 bierek ok. 13 milionów.
    Przy 32 bierkach możliwy jest jednak tylko jeden zestaw, taki jak przy rozpoczynaniu partii (bez żadnego bicia nie jest możliwa promocja piona).

    Niestety, bardziej kłopotliwe jest w miarę dokładne określenie ilości możliwych rozmieszczeń na szachownicy poszczególnych zestawów bierek. A te ilości są o rzędy wielkości wyższe od poprzednich liczb i to one decydują o końcowym rezultacie.
    Dwie bierki (2 króle) można rozmieścić na szachownicy na 3.612 sposobów (króle nie mogą się szachować).
    Dla 14 bierek (przyjąłem tu, poza królami, białego hetmana, 2 białe wieże, 4 białe piony, czarnego hetmana, czarną wieżę i 3 czarne piony) otrzymałem 6.1021 możliwych rozmieszczeń.
    Największe liczby możliwych pozycji (rzędu 1029 do 1033) otrzymywałem dla ilości bierek od 22 do 25.
    Te liczby skorygowane są już współczynnikami, mającymi wyeliminować "nielegalne" pozycje (np. obydwa króle są szachowane, liczba promowanych pionów większa, niż to możliwe przy danej ilości bierek, wszystkie piony jednego koloru na liniach "a" i "b", piony czy np. wieża za barierą pionów przeciwnika, itp.).

    Ostateczny wynik, czyli ogólna ilość możliwych pozycji na szachownicy, wg moich prób obliczeń wahał się w granicach od 1038 do 1041. Myślę, że można tu z powodzeniem przyjąć liczbę 1040.
    Ta liczba jest o wiele rzędów wielkości mniejsza, niż oszacowana wcześniej ilość możliwych kontynuacji partii ( 10134 ).


    Jan K. Nowakowski
    Opole, 2000r.





    do góry


    stat4u