1. Dom
  2. Pytanie i odpowiedź
  3. Obecnie znany najlepszy algorytm (y) do szachów komputerowych?

Obecnie znany najlepszy algorytm (y) do szachów komputerowych?

2010-01-08 17 views

Odpowiedz

3

Minimax

Jeśli potrzebują dogłębnej wiedzy na temat algorytmów sztucznej inteligencji, myślę "artificial intelligence modern approach" książka jest najlepszym źródłem.

Źródło

2010-01-08 08:21:42

+2

To byłby * jeden * część algorytmu gry w szachy. Jednak minimax nie jest sam w sobie algorytmem szachowym. – Tarydon

1

to bezpieczny zakład jako punkt wyjścia. Spoglądałeś tam?

Rybka wydaje się być pretendentem.

Źródło

2010-01-08 08:21:57 Tarydon

+0

Zgadzam się, Wikipedia jest dobrym miejscem do patrzenia, ale Rybka jest zamkniętym źródłem, więc prawdopodobnie niewiele pomoże –

+0

@Dave: Prawda, ale rozwiązuje problem anarhikos * tylko chcąc nauczyć się nazwy algorytmów *. – Tarydon

+1

@Tarydon - Rybka to nazwa silnika _ss_. Ponieważ jest to zamknięte źródło, nikt (oprócz autora) nie wie, jakich algorytmów używa. –

20

Ogólna strategia w algorytmach gier to strategia minimax, wzbogacona o alpha-beta pruning. Algorytm minimax znajduje najlepszy ruch, a przycinanie alfa-beta zapobiega przechodzeniu w gałęzie drzewa gry, które nie mogą dać lepszego wyniku niż poprzednie gałęzie.

Drzewo gry w szachy jest jednak zbyt duże, aby można było je dokładnie zbadać. Właśnie dlatego komputerowe silniki szachowe badają drzewo tylko do określonej głębokości, a następnie wykorzystują różne metody do oceny pozycji. Wiele z tych metod opiera się na heurystyce. Poważny program do gry w szachy będzie miał bibliotekę otworów, dzięki czemu będzie mógł grać na początku, po prostu sprawdzając tę ​​bibliotekę i nie sprawdzając drzewa gry. Wreszcie, wiele gier końcowych jest całkowicie rozwiązanych, a te są również zaprogramowane jako biblioteka.

Źródło

2010-01-08 08:34:34 JaakkoK

+0

Odpowiednik minimax nazywa się negamax. Różnica polega na tym, że wynik jest zanegowany przy każdej zmianie głębokości w drzewie. W ten sposób obaj gracze starają się zmaksymalizować wynik (gdzie w minimaksie próbuje się go zminimalizować). Nie jestem pewien, co to robi w oknie alfa/beta. Czy staje się tylko jedną wartością? – phkahler

+2

należy zauważyć, że funkcja oceny pozycji jest prawdopodobnie najważniejszym aspektem silnika szachowego przy określaniu jego wytrzymałości. W rzeczywistości jest to prawdopodobnie jedyny obszar, w którym występuje nowość w większości silników szachowych. Na przykład funkcja oceny pozycji Rybki została zaprojektowana przez 5 lat (jeśli irc) przez bardzo silnych graczy. W pewnym sensie funkcja oceny jest tym, co daje komputerową intuicję dotyczącą pozycji szachowej, fundamentalnie ważnej części każdej gry w szachy i ortogonalnie względem innych zagadnień, takich jak taktyka w grze. – ldog

+0

@gmatt - tylko częściowo prawda ... agresywne przycinanie jest częścią tego, co sprawia, że ​​Rybka jest tak silna, a badania w tym zakresie nie są zbyt stare. Rozszerzone przycinanie bezużyteczne, ograniczone żyletkowanie i adaptacyjne przycinanie z zerowym ruchem były najnowocześniejsze w tej dziedzinie mniej niż dziesięć lat temu – tbischel

0

Wiele algorytmów stosowanych w programowaniu szachów opisano na stronie internetowej http://chessprogramming.wikispaces.com/ . Dostępnych jest kilka programów open source, które implementują te algorytmy.

Źródło

2010-01-11 08:54:08

Powiązane problemy

 Powiązane problemy