Zagadnienia matematyczne

Liczba Shannona

Popularnym faktem naukowym jes to że, ilość kombinacji szachownicy jest większa niż
liczba atomów w obserwowalnym świecie.
około: 1080
Liczbą kombinacji szachowych jest nazywana liczbą shannona. - 10120. Wartość została określona na podstawie obserwacji partii szachowych w których było około 30 możliwości na każdy ruch i 80 posunięć - 3080.
Claude Shannon
Amerykański matematyk, jeden z twórców teorii informacji.
Jako jeden z pierwszych pojął ważność kodu binarnego.
Stworzył 'Matematyczną teorię komunikacji'.
wyprowadził tę liczbę by udowodnić, że komputer nie jest w stanie przeanalizować każdego możliwego ruchu, ponieważ w momencie gdy obliczałby jedną grę na mikrosekundę zajęłoby mu to czas do końca wszechświata by dokończyć obliczenia. Jednakże jeżeli chcielibyśmy ograniczyć te kombinacje do tych racjonalnych - czyli tych w których dwóch zawodników chce wygrać, liczba kombinacji wynosiłaby około 1048. W swojej książce "Chess Metaphors" Diego Rasskin-Gutman wskazuje, że gracz, który rozpatruje osiem ruchów w przód, wyobraża sobie tyle gier, ile jest gwiazd w galaktyce.
Liczba ruchów Liczba możliwych kombinacji
1 20
2 400
3 8,902
4 197,281
... ...
9 2,439,530,234,167
10 69,352,859,712,417

Problem skoczka szachowego

Do poprawnego rozwiązania tego problemu potrzebna jest znajomość zasady poruszania się skoczka po szachownicy - charakterystyczne "L". Istotą problemu jest, rozpoczynając z wyznaczonego pola na szachownicy, odwiedzić wszystkie pola szachownicy tak aby każde z nich było odwiedzone tylko raz. Problem intrygował matematyków od wieków np. Leonarda Eulera który pod koniec XVIII w. opracował metodę pozwalającą na rozwiązanie problemu.

Rozwiązania problemu dzielą się na: zamknięte - z końcowej pozycji figura jest w stanie dojść do początku jednym ruchem, oraz otwarte - w których nie ma takiej możliwości. Istnieje
ponad 26 bilionów
26,534,728,821,064
rozwiązań zamkniętych na planszy 8x8. Nie wiadomo ile istnieje rozwiązań otwartych. Dzieki postępowi technologicznemu znaleziono 140 rozwiązań
'półmagicznych'
Kwadrat półmagiczny to tablica liczb składający się z n wierszy i n kolumn, w którego wpisano n2 nie powtarzających się liczb, w ten sposób, że suma liczb w każdym wierszu i kolumnie jest taka sama.kwadrat polmagicznyŹródło: Numberphile
. Nie istnieje żadne rozwiązanie w pełni magiczne.
Rozwiązanie zamknięte (Źródło: Numberphile)
Rozwiń rozwiązanie problemu
Wybierz pozycję startową dla skoczka. Następnie wybierając kolejno jeden z możliwych ruchów, spróbuj doprowadzić do zapełnienia całej planszy swoimi ruchami.

Rozwiązanie problemu skoczka szachowego

Poradnik krok po kroku jak rozwiązać problem metodą "Czterech diamentów".

Podział szachownicy

Możliwe diamenty

Algorytm ruchów

Istnieje wiele różnorodnych sposobów na rozwiązanie tego problemu. Niestety większość z nich wymaga zapamiętania długich kombinacji numerów lub wizualizowania skomplikowanych wzorów geometrycznych. Przedstawiony sposób pozwala na rozwiązanie tego problemu w prostych krokach, pamiętając jedynie metodę działania. Analiza tego rozwiązania pokazuje jak ważnym jest rozdzielanie dużych problemów w mniejsze z którymi łatwiej sobie poradzić.

Pierwszym krokiem do rozwiązania tego problemu jest podzielenie szachownicy na 4 kwadraty o 4 wierszach i 4 kolumnach. Każdemu nowo powstałemu kwadratowi należy przydzielić odpowiedni numer.

Podział szachownicy

Do następnego kroku potrzebne jest poznanie tytułowych 'diamentów'. Są to 4 figury, możliwe do zapisania na siatce 4x4. Każda z figur jest zbudowana według zasady poruszania się skoczkiem. Gdy nałożymy wszystkie diamenty na jedną siatkę, zauważymy że wierzchołki tych figur pokrywają cały kwadrat.

Górny diament
Dolny diament
Lewe koło
Prawe koło

Ostatnim krokiem jest przestrzeganie ściśle określonych zasad algorytmu poniżej.

  • Pierwszym krokiem jest wybranie dowolnego miejsca na szachownicy
  • Następnie sprawdzamy w którym kwadracie i diamencie znajduje się nasz skoczek
  • Wiedząc, że zajęcie całego diamentu jest dostępne w 3 ruchach, wybieramy kolejno 3 wierzchołki zajmowanego diamentu.
  • Po wypełnieniu zajmowanego diamentu, skoczek powinien znajdować się na miejscu z którego jest w stanie przenieść się do tego samego typu diamentu w następnym kwadracie.
  • Wypełniamy pozostałe ćwiartki pierwszym diamentem.
  • Po wypełnieniu ostatniej ćwiartki, należy sprawdzić jakie możliwości ruchu są dostępne, wybieramy tą możliwość która znajduje się w innej ćwiartce i rozpoczynamy nowy diament.
  • Powtarzamy algorytm z pozostałymi diamentami, przy poprawnym wyborze pól skoczek zawsze powinien zająć wszystkie pola szachownicy
Przejdź do rozwiązywania problemu

Problem 8 hetmanów

Hetman jest najsilniejszą figurą na szachownicy. Istotą problemu jest umieszczenie 8 hetmanów tak, aby wzajemnie się nie atakowały. Carl Friedrich Gauss poświęcił temu zagadnieniu sporo czasu, czego efektem było wyszczególnienie wszystkich możliwych kombinacji. To zadanie ma
92 rozwiązań
12 prawdziwych rozwiązań i 80 wynikających z rotacji i odbić lustrzanych
. Ilość kombinacji ustawień ośmiu figur na szachownicy możemy obliczyć ze wzoru na kombinację bez powtórzeń: $$ \binom{64}{56} = {64! \over 8!\cdot(64-56)!} = 4\,426\,165\,368 $$ Posiadając te informacje wiemy, że losowo układając 8 hetmanów na szachownicy jest \({23 \over 1106541342}\%\) szansy na to, że układ będzie spełniał wymagania problemu.
Wizualizacja algorytmu rekurencyjnego szukającego rozwiązania problemu 8 hetmanów
(źródło: Wikimedia commons)
Rozwiń przykładowe rozwiązanie problemu
Rozmieść 8 hetmanów tak aby żaden z nich nie atakował innego. Jeżeli uznasz, że chcesz cofnąć swój ruch kliknij na ustawionego hetmana. Zielone pola są w obszarze ataku figury.

Rozwiązanie problemu 8 hetmanów

Przykładowe rozwiązanie wykorzystujące własności symetrii.

Nie da się opisać jednym wzorem wszystkich rozwiązań problemu 8 hetmanów. Znając jedno rozwiązanie możemy przez proste transformacje wyprowadzić 8 kombinacji układów figur poprzez rotację i odbicie lustrzane. Przedstawiony sposób znacznie ułatwia zapamiętanie układu rozwiązującego to zagadnienie.

  • Pierwszym krokiem jest ustawienie hetmana na pole C1
  • Następnie ustawiamy hetmana na polu F8 które jest odbiciem lustrzanym pola pierwszego hetmana.
  • W celu wybrania kolejnej pozycji wyobrażamy sobie ruchy skoczka z pozycji C1
  • Wybieramy kombinację dwóch pól które nie są na tej samej linii.
  • Następne dwie figury ustawiamy na polach które są odbiciem lustrzanych poprzednich.
  • Pozostałe dwie figury ustawiamy na pozostałych nieatakowanych miejscach.

Problem 4 skoczków

Ten problem matematyczno-szachowy pochodzi z książki "Algorithmic Puzzles" autorstwa Anany Levitin oraz Marii Levitin. Problem czterech skoczków jest często stosowany na rozmowach rekrutacyjnych by sprawdzić radzenie sobie z problemami i technikę rozwiązywania. Na rogach planszy 3x3 rozstawiono cztery skoczki. Istotą problemu jest przeniesienie każdej figury na przeciwny narożnik planszy za pomocą ruchu skoczka i oszacowanie jaka będzie najmniejsza możliwa liczba ruchów doprowadzająca do rozwiązania problemu. Sposób rozumowania metodą grafów:

Jednym z założeń zadania jest to, że będziemy poruszali się skoczkami zgodnie z zasadami szachowymi. W początkowej fazie od każdego skoczka prowadzimy możliwe ruchy.

Krok 1/4
Liczba ruchów: 0 Za pomocą interaktywnej planszy oblicz ile ruchów jest potrzebnych by przenieść każdego ze skoczków na przeciwny narożnik. By wybrać figurę którą chcesz zrobić ruch kliknij na nią. Po najechaniu na skoczka wyświetli się pole na którym powinien skończyć rozgrywkę.

Algorytm Minimax

Ten algorytm jest powszechnie wykorzystywany w programach grających w szachy. Polega na sprowadzeniu aktualnego układu szachownicy do jednej opcji, z której możemy przejść do wielu następnych. Algorytm często wizualizowany jest jako drzewo binarne, w którym każdy punkt reprezentuje wybrane ułożenie figur na szachownicy, a jego wartość jest wyrażana w zależności od ustalonych priorytetów programu (Najczęściej ilość figur białych i czarnych na szachownicy). Ten algorytm jest wykorzystywany w grach, gdzie
nie ma ukrytych informacji
Przykładem takich gier są szachy, Go, kółko i krzyżyk a przeciwieństwem poker
w którym zawodnicy nie wiedzą o możliwościach przeciwnika.
i gdzie ruchy następują naprzemiennie.

Algorytm wykorzystuje rekurencję by oznaczyć wartości kolejnych wierzchołków drzewa binarnego. Znając wartości poszczególnych układów na wyznaczonej warstwie, w zależności od tego który gracz ma wtedy ruch, może wybrać najkorzystniejszą krawędź dla niego. Powtarzając tę czynność dla każdej warstwy, w początkowym punkcie drzewa gracz będzie w stanie określić ścieżkę, zgodnie z którą powinien rozgrywać partię by osiągnąć najlepszy wynik.
Wizualizacja działania algorytmu minimax. Kolor kropek wskazuje na kolor figur gracza który ma wykonywać ruch. Na potrzebę animacji możliwe ruchy zostały ograniczone do dwóch. Celem białego gracza jest jak największa liczba, czarnego najmniejsza. (Źródło: Sebastian Lague)