Chinook (program komputerowy) - Chinook (computer program)
Chinook to program komputerowy, który gra w warcaby (znane również jako warcaby). Został opracowany w latach 1989-2007 na Uniwersytecie Alberty przez zespół kierowany przez Jonathana Schaeffera, w skład którego wchodzili Rob Lake , Paul Lu , Martin Bryant i Norman Treloar . Algorytmy programu obejmują książkę otwierającą, która jest biblioteką ruchów otwierających z gier rozgrywanych przez arcymistrzów warcabów; algorytm głębokiego wyszukiwania; dobra funkcja oceny ruchu; oraz bazę danych na koniec gry dla wszystkich pozycji z ośmioma figurami lub mniej. Cała wiedza Chinook została zaprogramowana przez jego twórców, a nie przyswojona za pomocą systemu sztucznej inteligencji .
Mistrz Świata Człowiek kontra Maszyna
Chinook to pierwszy program komputerowy, który zdobył tytuł mistrza świata w rywalizacji z ludźmi. W 1990 roku zdobył prawo do gry w Mistrzostwach Świata ludzi, zajmując drugie miejsce za Marion Tinsley w zawodach narodowych USA. Początkowo American Checkers Federation i English Drafts Association były przeciwne udziałowi komputera w ludzkich mistrzostwach. Kiedy Tinsley zrezygnował ze swojego tytułu w proteście, ACF i EDA stworzyły nowy tytuł Man vs. Machine World Championship i rywalizacja trwała dalej. Tinsley wygrał z czterema zwycięstwami do dwóch Chinook, z 33 remisami.
W rewanżu Chinook został ogłoszony Mistrzem Świata Człowiek-Maszyna w warcabach w 1994 roku w meczu z Marion Tinsley po sześciu remisowych grach i wycofaniu się Tinsleya z powodu raka trzustki. Chociaż Chinook został mistrzem świata, nigdy nie pokonał najlepszego gracza w warcaby wszechczasów, Tinsleya, który był znacznie lepszy nawet od swojego najbliższego rówieśnika.
W 1995 roku Chinook obronił swój tytuł człowiek-maszyna przeciwko Donowi Lafferty'emu w 32-meczowym meczu. Ostateczny wynik to 1-0 z 31 remisami Chinook nad Lafferty. Po meczu Jonathan Schaeffer zdecydował, że nie pozwoli Chinookowi więcej rywalizować, ale zamiast tego spróbuje rozwiązać warcaby. W tym czasie został wyceniony na 2814 Elo . Rozwiązanie zostało osiągnięte, a wynik opublikowany w 2007 roku.
Algorytm
Algorytm programu Chinook zawiera książkę otwierającą, bibliotekę ruchów otwierających z gier rozgrywanych przez arcymistrzów; algorytm głębokiego wyszukiwania; dobra funkcja oceny ruchu; oraz bazę danych na koniec gry dla wszystkich pozycji z ośmioma figurami lub mniej. Liniowa, ręcznie wykonana funkcja oceny uwzględnia kilka cech planszy, w tym liczbę pionów, liczbę króli, uwięzionych królów, turę, uciekające warcaby (nieograniczoną ścieżkę do króla) i inne mniejsze czynniki. Cała wiedza Chinook została zaprogramowana przez jego twórców, a nie przyswojona przez sztuczną inteligencję.
Oś czasu
- 1997 - Jonathan Schaeffer pisze książkę o Chinook zatytułowaną One Jump Ahead: Challenging Human Supremacy in Checkers . Zaktualizowana wersja książki została opublikowana w listopadzie 2008 r.
- 24 maja 2003 r. - Chinook uzupełnia swoją bazę 10 elementów z 5 elementami z każdej strony.
- 2 sierpnia 2004 - Drużyna Chinook ogłasza, że otwarcie turnieju w warcaby o nazwie White Doctor (10-14 22-18 12-16) zakończyło się remisem.
- 18 stycznia 2006 - Zespół Chinook ogłasza, że otwarcie 09-13 21-17 05-09 okazało się remisem.
- 18 kwietnia 2006 - Zespół Chinook ogłasza, że otwarcie 09-13 22-17 13-22 zakończyło się remisem.
- 10 marca 2007 - Jonathan Schaeffer ogłasza (na konferencji ACM SIGCSE 2007), że ostateczne rozwiązanie dla warcabów spodziewane jest w ciągu 3-5 miesięcy.
- 19 lipca 2007 - Czasopismo Science publikuje artykuł zespołu Schaeffera "Warcaby rozwiązane", przedstawiający ich dowód na to, że najlepszym zawodnikiem, który może osiągnąć grając przeciwko graczowi posiadającemu doskonałe informacje, jest remis.