Algorytmy minimax i alfa-beta cięć w zastosowaniu do programów szachowych
| dc.contributor.advisor | Kawa, Rafał | |
| dc.contributor.author | Markowska Magdalena | |
| dc.date.accessioned | 2017-07-01T14:43:14Z | |
| dc.date.available | 2017-07-01T14:43:14Z | |
| dc.date.issued | 2006 | pl |
| dc.description.abstract | Zasadniczym celem pracy było przedstawienie algorytmu mini-max, który jest podstawowym algorytmem pozwalającym każdemu programowi szachowemu opracować strategie grania, a także algorytmu alfa-beta cięć z jego udoskonaleniami. Praca ta składa się z trzech części. W pierwszej części został przedstawiony ponad pół wieczny okres dorobku metod programowania rozwoju najpierw maszyn a potem programów do gry w szachy. W drugim rozdziale został przedstawiony algorytm minimax wraz z jego rozwinięciem – algorytm alfa-beta cięć. Algorytm minimax jest podstawowym algorytmem wykorzystywanym w mechanizmie programowania gier logicznych, jest on stosowany do oszacowania wartości danej pozycji. Jego zadaniem jest znalezienie najbardziej trafnego posunięcia, które przyniesie zwycięstwo, a porażkę przeciwnikowi. W kolejnym rozdziale zostały omówione różnorodne metody udoskonalenia algorytmu alfa-beta, takie jak: przeszukiwanie minimalnego okna, PVS, MTD(f), przeszukiwanie w przód, mechanizmy kolejności ruchów (heurystyki: ruchów morderców (killer moves), historii i w oparciu o pusty ruch), iteracyjne pogłębianie, tablice transpozycji, ProbCut i MultiProbCut. Autor niniejszej pracy zakłada, że czytelnik posiada postawy algorytmów i minimalną wiedzę szachową. Z algorytmu mini-max z cięciami alfa-beta wynika, że przeglądanie wszystkich gałęzi drzewa nie jest konieczne. Algorytm ten daje taki sam rezultat jak bez cięć, ale jest o wiele bardziej wydajny. Zazwyczaj podwaja ilość półruchów, które mogą być przeszukane w danym czasie. Udoskonalenia takie jak heurystyki kolejności ruchów, iteracyjne pogłębianie, Pro-bCut i Multi-ProbCut a także użycie tablic transpozycji powoduje, że każdy program gra inaczej i znacznie szybciej. Metody te są skomplikowane, ale właściwa ich implementacji i współgranie decyduje o sile grania programu. | pl |
| dc.identifier.uri | http://hdl.handle.net/11199/10056 | |
| dc.language.iso | pl | pl |
| dc.rights | licencja niewyłączna | pl |
| dc.subject | gry w szachy | pl |
| dc.subject | gry komputerowe | pl |
| dc.subject | algorytmy minimax | pl |
| dc.subject | algorytm alfa-beta cięć | pl |
| dc.title | Algorytmy minimax i alfa-beta cięć w zastosowaniu do programów szachowych | pl |
| dc.type | bachelorThesis | pl |