Komputer Otello - Computer Othello

Computer Othello odnosi się do architektury komputerowej obejmującej sprzęt komputerowy i oprogramowanie komputerowe zdolne do grania w grę Othello .

Dostępność

Istnieje wiele programów Othello, takich jak NTest , Saio, Edax , Cassio, Pointy Stone, Herakles, WZebra i Logistello, które można bezpłatnie pobrać z Internetu . Programy te, uruchomione na dowolnym, zaktualizowanym komputerze , mogą grać w gry, w których najlepsi gracze są z łatwością pokonani. Dzieje się tak dlatego, że chociaż konsekwencje ruchów są przewidywalne zarówno dla komputerów, jak i dla ludzi, komputery są lepsze w ich przewidywaniu.

Techniki wyszukiwania

Programy komputerowe Othello wyszukują wszelkie możliwe legalne ruchy za pomocą drzewa gry . Teoretycznie badają wszystkie pozycje/węzły, gdzie każdy ruch jednego gracza nazywany jest „ply” . To wyszukiwanie jest kontynuowane aż do określonej maksymalnej głębokości wyszukiwania lub program określi, że osiągnięta została końcowa pozycja „liścia”.

Naiwna implementacja tego podejścia, znana jako Minimax lub Negamax , może przeszukiwać tylko niewielką głębokość w praktycznym czasie, więc opracowano różne metody, aby znacznie zwiększyć szybkość wyszukiwania dobrych ruchów. Są one oparte na przycinaniu Alpha-beta , Negascout , MTD(f) , NegaC*. Algorytm alfabetu to metoda przyspieszania procedury wyszukiwania Minimax poprzez odcinanie przypadków, które i tak nie będą używane. Ta metoda wykorzystuje fakt, że każdy inny poziom w drzewie będzie maksymalizowany, a każdy inny minimalizowany.

W celu zmniejszenia rozmiaru przeszukiwanego drzewa stosuje się również kilka heurystyk: dobre porządkowanie ruchów, tabela transpozycji i wyszukiwanie selektywne.

Aby przyspieszyć wyszukiwanie na maszynach z wieloma procesorami lub rdzeniami, można zaimplementować „przeszukiwanie równoległe” . Z grą Othello przeprowadzono kilka eksperymentów, takich jak ABDADA lub APHID. W ostatnich programach YBWC wydaje się preferowanym podejściem.

Cięcie wieloprobowe

Multi-ProbCut to heurystyka używana w przycinaniu drzewa wyszukiwania w fazie alfa-beta . Heurystyka ProbCut szacuje wyniki oceny na głębszych poziomach drzewa wyszukiwania przy użyciu regresji liniowej między głębszymi i płytszymi wynikami. Multi-ProbCut rozszerza to podejście na wiele poziomów drzewa wyszukiwania. Sama regresja liniowa jest wyuczona podczas poprzednich przeszukiwań drzewa, dzięki czemu heurystyka jest rodzajem dynamicznej kontroli wyszukiwania. Jest to szczególnie przydatne w grach takich jak Othello, gdzie istnieje silna korelacja między wynikami ocen na głębszych i płytszych poziomach.

Techniki oceny

Istnieją trzy różne paradygmaty tworzenia funkcji oceny.

Tabele dysk-kwadrat

Różne kwadraty mają różne wartości - rogi są dobre, a kwadraty przy rogach są złe. Niezależnie od symetrii, na planszy jest 10 różnych pozycji, a każdej z nich przypisana jest wartość dla każdej z trzech możliwości: czarny krążek, biały krążek i pusta. Bardziej wyrafinowanym podejściem jest posiadanie różnych wartości dla każdej pozycji na różnych etapach gry; np. rzuty rożne są ważniejsze w otwarciu i wczesnej środkowej fazie gry niż w końcówce.

Oparte na mobilności

Większość ludzkich graczy stara się zmaksymalizować mobilność (liczba dostępnych ruchów) i zminimalizować dyski graniczne (dyski przylegające do pustych pól). Obliczana jest mobilność gracza i mobilność przeciwnika, a także potencjalna mobilność gracza i potencjalna mobilność przeciwnika. Te środki można znaleźć bardzo szybko i znacznie zwiększają siłę gry. Większość programów ma wiedzę na temat konfiguracji krawędzi i narożników i stara się zminimalizować liczbę dysków we wczesnej grze środkowej, co jest kolejną strategią stosowaną przez graczy.

Współczynniki oparte na wzorcu / współczynniki wzorca

Maksymalizację mobilności i minimalizację granic można podzielić na lokalne konfiguracje, które można sumować; zwykłą implementacją jest ocena każdego wiersza, kolumny, konfiguracji przekątnej i narożnika osobno i zsumowanie wartości, wiele różnych wzorów musi zostać ocenionych. Proces określania wartości dla wszystkich konfiguracji odbywa się poprzez pobranie dużej bazy danych gier rozegranych między silnymi graczami i obliczenie statystyk dla każdej konfiguracji na każdym etapie gry ze wszystkich gier.

Najczęstszy wybór przewidywania ostatecznej różnicy dysków wykorzystuje ważoną miarę różnicy dysków, w której wygrywająca strona otrzymuje premię odpowiadającą liczbie dysków.

Otwieranie książki

Książki otwierające wspierają programy komputerowe, oferując popularne otwarcia, które są uważane za dobry sposób na przeciwdziałanie słabym otworom. Wszystkie silne programy wykorzystują otwieranie książek i automatycznie aktualizują swoje książki po każdej grze. Aby przejrzeć wszystkie pozycje ze wszystkich partii w bazie danych gry i określić najlepszy ruch, który nie został rozegrany w żadnej grze w bazie danych, tabele transpozycji służą do rejestrowania pozycji, które zostały wcześniej przeszukane. Oznacza to, że te pozycje nie muszą być ponownie przeszukiwane. Jest to czasochłonne, ponieważ dla każdej pozycji należy przeprowadzić głębokie wyszukiwanie, ale po wykonaniu tej czynności aktualizacja książki jest łatwa. Po każdym rozegranym meczu wszystkie nowe pozycje są przeszukiwane pod kątem najlepszego odchylenia.

Inne optymalizacje

Szybszy sprzęt i dodatkowe procesory mogą poprawić możliwości programu grającego w Othello, takie jak głębsze wyszukiwanie warstw.

Rozwiązywanie Otella

Podczas rozgrywki gracze naprzemiennie wykonują ruchy. Gracz-człowiek używa czarnych żetonów, podczas gdy komputer używa białych. Grę rozpoczyna człowiek. Otello jest mocno rozwiązany na planszach 4×4 i 6×6, gdzie drugi gracz (biały) wygrywa w idealnej grze . Pozostaje nierozwiązana na standardowej planszy 8×8, ale analiza komputerowa daje tysiące linii rysowania lub ścieżek do losowania, chociaż żadna taka linia nie została w pełni udowodniona.

Otello 4 × 4

Othello 4x4 ma bardzo małe drzewo gry i zostało rozwiązane w czasie krótszym niż jedna sekunda przez wiele prostych programów Othello wykorzystujących metodę Minimax, która generuje wszystkie możliwe pozycje (prawie 10 milionów). W rezultacie białe wygrywają z przewagą +8 (3-11).

Otello 6 × 6

Othello 6x6 zostało rozwiązane w czasie krótszym niż 100 godzin przez wiele prostych programów Othello wykorzystujących metodę Minimax, która generuje wszystkie możliwe pozycje (blisko 3,6 biliona). W rezultacie white wygrywa z przewagą +4 (16-20).

Otello 8 × 8

Rozmiar drzewa gry Othello 8x8 jest szacowany na 10 ⁵⁴ węzłów, a liczba legalnych pozycji jest szacowana na mniej niż 10 ²⁸ . Gra pozostaje nierozwiązana. Rozwiązaniem może być użycie intensywnych obliczeń z najlepszymi programami na szybkim sprzęcie równoległym lub poprzez obliczenia rozproszone .

Niektóre najlepsze programy od wielu lat rozszerzają swoje książki. W rezultacie wiele linii to w praktyce remisy lub wygrane dla obu stron. Jeśli chodzi o trzy główne otwory ukośne, prostopadłe i równoległe, wydaje się, że zarówno ukośne, jak i prostopadłe otwory prowadzą do rysowania linii, podczas gdy otwarcie równoległe jest wygraną dla czarnych. Drzewo rysunkowe wydaje się również większe po otworze ukośnym niż po otworze prostopadłym. Równoległe otwarcie ma duże zalety dla czarnego gracza, pozwalając mu zawsze wygrywać w doskonałej grze.

Kamienie milowe w komputerze Otello


	a	b	C	D	mi	F	g	h
1									1
2									2
3									3
4									4
5									5
6									6
7									7
8									8
	a	b	C	D	mi	F	g	h

Logistello kontra Takeshi Murakami (czwarty mecz)

1977 : Scientific American dokonało najwcześniejszego znanego opublikowanego odniesienia do programu Othello/Reversi, napisanego przez NJD Jacobsa w BCPL . W październiku firma BYTE opublikowała „Othello, a New Ancient Game” jako program do wpisywania w języku BASIC .
1977 : Creative Computing opublikował wersję Otella napisaną przez Eda Wrighta w FORTRAN .
1978 : Nintendo wypuszcza gier wideo Computer Othello w salonach .
1980 : Program Othello The Moor (napisany przez Mike'a Reeve'a i Davida Levy'ego ) wygrał jeden mecz w sześciomeczowym meczu z mistrzem świata Hiroshi Inoue. Peter W Frey z Northwestern University omawiał strategie komputerowe i ludzkie Othello w BYTE oraz omawiał swoją grę TRS-80 Othello, która, jak twierdzi Frey, z łatwością pokonała wersję Wrighta działającą na CDC 6600 . Paul Rosenbloom z Carnegie Mellon University opracował IAGO , który zajął trzecie miejsce w turnieju komputerowym Northwestern University. Kiedy IAGO grało w Wrzosowisko, IAGO lepiej radziło sobie z przejmowaniem pionów na stałe i ograniczaniem mobilności przeciwnika.
1981 : IAGO biegnący na DEC KA10 ukończył przed 19 innymi zawodnikami w Santa Cruz Open Othello Tournament na Uniwersytecie Kalifornijskim w Santa Cruz , z jedynym niepokonanym rekordem. Gra oparta na TRS 80 Charlesa Heatha zajęła drugie miejsce. Silniki oparte na procesorach mikrokomputerowych zajmowały miejsca od drugiego do siódmego, wyprzedzając kilka komputerów typu mainframe i minikomputerów; Frey spekulował, że dzieje się tak dlatego, że komputer Othello nie korzysta z kilku zalet większych komputerów, takich jak szybsza arytmetyka zmiennoprzecinkowa .
Późne lata osiemdziesiąte : Kai-Fu Lee i Sanjoy Mahajan stworzyli program Othello BILL , który był podobny do IAGO, ale zawierał naukę Bayesa. BILL niezawodnie pokonał IAGO.
1992 : Michael Buro rozpoczął pracę nad programem Logistello Othello . Techniki wyszukiwania Logistello, funkcja oceny i baza wiedzy o wzorcach były lepsze niż we wcześniejszych programach. Logistello udoskonalił swoją grę, rozgrywając ponad 100 000 gier przeciwko sobie.
1997 : Logistello wygrał każdy mecz w sześciomeczowym meczu z mistrzem świata Takeshi Murakami. Chociaż nie było wątpliwości, że programy Othello są silniejsze od ludzi, minęło 17 lat od ostatniego meczu między komputerem a panującym mistrzem świata. Po meczu z 1997 roku nie było już żadnych wątpliwości: Logistello był znacznie lepszy niż jakikolwiek człowiek.
1998 : Michael Buro przechodzi na emeryturę Logistello. Zainteresowanie badawcze Othello nieco osłabło, ale niektóre programy, w tym Ntest, Saio, Edax, Cassio, Zebra i Herakles, nadal były rozwijane.
2004 : Ntest stał się najsilniejszym programem, znacznie silniejszym niż Logistello.
2005 : Ntest, Saio, Edax, Cyrano i Zebra stali się znacznie silniejsi niż Logistello. Ntest i Zebra przeszli na emeryturę.
2011 : Saio , Edax i Cyrano , stały się znacznie szybsze niż Logistello i inne programy.

Languages

In other projects