6 marca 2021

Silniki szachowe - szachy komputerowe

Silnik szachowy to specjalistyczne oprogramowanie, które w dużym skrócie potrafi analizować pozycje szachowe i wybierać (teoretycznie) najlepsze posunięcia w danej pozycji. Historia maszyn do gry w szachy jest starsza niż mogłoby wam się wydawać. Pierwsze próby stworzenia takowej maszyny sięgają 1846 roku, w którym to Charles Babbage rozważał nauczenia gry w szachy swojej maszyny „Analitycal Engine”, jednak pierwszą faktyczną maszyną potrafiącą grać (w ograniczonym stopniu) stworzono około roku 1890.

Od tamtego momentu tworzono coraz to nowsze, szybsze i bardziej dokładne silniki, które w tym momencie potrafią już ograć szachowych arcymistrzów.

szachy komputerowe

Za najlepsze posunięcia w szachach komputerowych odpowiada specjalistyczne oprogramowanie - silnik szachowy.

Sposób działania

Istnieje wiele technik wykorzystywanych przy obliczaniu najlepszych ruchów w pozycji przez silniki szachowe, a to są najpopularniejsze:

  • algorytm min-max – w tym algorytmie chodzi o minimalizowanie maksymalnie możliwych strat. W skrócie: ruch x białych jest najlepszy (nawet jeśli prowadzi do porażki) po uwzględnieniu najlepszych odpowiedzi czarnych, a najlepsza odpowiedź czarnych na ruch x jest wybierana po uwzględnieniu możliwych odpowiedzi białych – i tak dalej.
  • algorytm alfa-beta - pozwala ograniczyć liczbę ocenianych wariantów. Chodzi w nim o to, aby nie liczyć wariantu po znalezieniu lepszego. Innymi słowy, jeśli w danym wariancie oponent przy najlepszej grze uniknie pozycji do której dążył silnik, to przerywa on analizę wariantu prowadzącego do tej pozycji.
  • killer heuristic - zwiększa efektywność liczenia wariantów w kolejnych iteracjach przez sprawdzanie w danej podgałęzi drzewa w pierwszej kolejności tych posunięć, które spowodowały odcięcie pozostałych wariantów w innej pozycji na tej samej głębokości drzewa (te posunięcia to tzw. killer moves). Jeśli odcięcie najlepiej ocenianego wariantu nastąpiło dzięki znalezieniu nowego ruchu, zastępuje on wcześniejszy „killer move” (lub jeden z kilku przechowywanych przez silnik).

W praktyce wygląda to tak, że program musi ocenić pozycję, wybrać ruchy-kandydatów, uszeregować je, obliczyć warianty i ocenić nowo powstające pozycje. A po każdym posunięciu tworzą się nowe ruchy-kandydaci i znów trzeba wybierać , a silniki stworzone są do tego, żeby wybierać te opcje jak najlepiej. Coś takiego nazywamy drzewem wariantów.

algorytm minimax

Algorytm min-max, alfa-beta oraz killer heuristic to najpopularniejsze techniki wykorzystywane przy obliczaniu najlepszych ruchów przez silniki szachowe.

AlphaZero

Do niedawna najsilniejszym oprogramowaniem szachowym był Stockfish, jednak został zdetronizowany przez AlphaZero – silnik stworzony przez Google. W turnieju rozegranym przez owe oprogramowania AlphaZero kompletnie zdominowało swojego przeciwnika z wynikiem: 25 zwycięstw, 25 remisów i 0 porażek grając białymi i 3 zwycięstwa, 47 remisów i 0 porażek grając czarnymi. Algorytm AlphaZero bazuje na wykorzystaniu głębokiej sieci neuronowej (deep neural network). Sieć neuronowa jest naszą próbą przełożenia ludzkich połączeń neuronowych na język komputerowy. Dzięki tej technologii silnik potrafi się uczyć i na bieżąco analizować swoje błędy.

AlphaZero ma również taką przewagę nad innymi silnikami, że uczy się gry na podstawie partii przegranych samemu ze sobą. AlphaZero po czterech godzinach grania z samym sobą, nauczył się wystarczająco dużo o szachach, aby przewyższyć ranking Stockfisha, pomimo faktu, że przeanalizował jedyne 0,1 procenta pozycji, które przeanalizował Stockfish.

Praktyczne użycie

W dzisiejszych czasach silniki szachowe są ogólnodostępne i może z nich korzystać każdy zainteresowany. Zastosowanie znajdują między innymi jako:

  • narzędzie do nauki gry dla początkujących i nie tylko
  • pomoc przy analizowaniu rozegranych partii
  • wsparcie dla komentatorów turniejów szachowych na żywo

Silniki szachowe są potężnymi narzędziami i niestety zdarza się, że są wykorzystywane przez graczy w celu nieuczciwego osiągnięcia zwycięstwa w partiach toczonych przez internet np. na platformie chess.com. Jest to oczywiście uznawane jako oszustwo i odpowiednio karane, także nie zachęcam do korzystania z oprogramowania w ten sposób.

Problem ośmiu hetmanów

Częstym problemem omawianym na naszych kursach z informatyki jest problem ośmiu hetmanów. Jest to ciekawy problem, który chciałbym po krótce omówić, gdyż jest on powiązany z tematem wpisu, oraz można go rozwiązać za pomocą algorytmu, co jest fajnym ćwiczeniem programistycznym. Jak dotąd, problemu tego nie było nigdy na maturze z informatyki, jednak nie jest pewne, czy się nie pojawi w przyszłym roku. Problem ten polega na rozstawieniu ośmiu hetmanów na szachownicy w taki sposób, aby wzajemnie się nie atakowały. Hetman jako figura szachowa porusza się w boki, do góry, do dołu, oraz po przekątnych. Ilość możliwych ustawień hetmanów na szachownicy po jednym w kolumnie to 16777216, czyli bardzo dużo. Zadaniem programu jest wyeliminowanie niepoprawnych ustawień i zostawienie tylko tych prawidłowych. Chcesz poznać więcej programistycznych ciekawostek? Zapraszam na nasz kurs!

problem 8 hetmanów

Problem 8 hetmanów to ciekawe ćwiczenie programistyczne.

Pierwsze próby stworzenia takowej maszyny sięgają 1846 roku, w którym to Charles Babbage rozważał nauczenia gry w szachy swojej maszyny „Analitycal Engine”, jednak pierwszą faktyczną maszyną potrafiącą grać (w ograniczonym stopniu) stworzono około roku 1890.

Najnowsze wpisy

Python a C++

Przeczytaj >>

Algorytm Euklidesa w języku Python

Przeczytaj >>

10 podstawowych funkcji Excela, które trzeba znać

Przeczytaj >>

Microsoft Access - Wprowadzenie

Przeczytaj >>

Bazy danych a relacje między tabelami

Przeczytaj >>

JESTEŚ AMBITNY?

Dołącz do nas jeszcze dziś i rozwijaj się w swojej ulubionej dziedzinie we współpracy z nauczycielami, którzy są autorami artykułów na naszym blogu!
POZNAJ OFERTĘ KUSÓW
© Ambitni Szkoła Informatyki 011111100101(2) | jesteś niemal gotowy!
crossmenu