Komputerowy Otello

Komputer Othello odnosi się do architektury komputera obejmującej sprzęt komputerowy i oprogramowanie komputerowe zdolne do grania w grę Othello . Jest również znany jako Reversi dla Microsoft Windows ( 1.0 - XP , 1985-2005) i Classic Mac OS (od 1984).

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 nowoczesnym komputerze , mogą grać w gry, w których najlepsi ludzie są łatwo pokonani. Dzieje się tak, ponieważ chociaż konsekwencje ruchów są przewidywalne zarówno dla komputerów, jak i dla ludzi, komputery lepiej je przewidują.

Techniki wyszukiwania

Programy komputerowe Othello wyszukują wszelkie możliwe legalne posunięcia za pomocą drzewa gry . Teoretycznie badają wszystkie pozycje/węzły, gdzie każdy ruch jednego gracza nazywa się „warstwą” . Wyszukiwanie to jest kontynuowane, dopóki nie zostanie osiągnięta określona maksymalna głębokość wyszukiwania lub program nie ustali, że osiągnięta została ostateczna pozycja „liścia”.

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

W celu zmniejszenia rozmiaru przeszukiwanego drzewa stosuje się również kilka heurystyk: dobra kolejność ruchów, tablica transpozycji i wyszukiwanie selektywne.

Aby przyspieszyć wyszukiwanie na komputerach z wieloma procesorami lub rdzeniami, można zaimplementować „wyszukiwanie 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 Multi-Prob

Multi-ProbCut to heurystyka używana do przycinania alfa-beta drzewa wyszukiwania. Heurystyka ProbCut szacuje wyniki oceny na głębszych poziomach drzewa wyszukiwania przy użyciu regresji liniowej między wynikami głębszymi i płytszymi. Multi-ProbCut rozszerza to podejście na wiele poziomów drzewa wyszukiwania. Sama regresja liniowa jest uczona podczas poprzednich przeszukiwań drzewa, co czyni heurystykę 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 ewaluacyjnych.

Stoły kwadratowe

Różne kwadraty mają różne wartości - rogi są dobre, a kwadraty obok rogów są złe. Pomijając symetrie, na planszy jest 10 różnych pozycji, a każdej z nich przypisana jest wartość dla każdej z trzech możliwości: czarnego dysku, białego dysku i pustego. Bardziej wyrafinowanym podejściem jest posiadanie różnych wartości dla każdej pozycji podczas różnych etapów gry; np. rzuty rożne są ważniejsze w debiucie i na początku gry środkowej niż w końcówce.

Oparte na mobilności

Większość graczy prowadzących ludzi dąży do maksymalizacji mobilności (liczby dostępnych ruchów) i minimalizacji dysków granicznych (dysków przylegających do pustych pól). Obliczana jest mobilność gracza i mobilność przeciwnika, a także potencjalna mobilność gracza i potencjalna mobilność przeciwnika. Środki te 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 próbuje zminimalizować liczbę dysków we wczesnej środkowej fazie gry, co jest kolejną strategią stosowaną przez graczy.

Współczynniki wzorcowe / wzorcowe

Maksymalizacja mobilności i minimalizacja granic można podzielić na lokalne konfiguracje, które można ze sobą sumować; zwykle implementacja polega na ocenie każdego wiersza, kolumny, konfiguracji przekątnej i narożnika osobno i zsumowaniu wartości, należy ocenić wiele różnych wzorców. Proces określania wartości dla wszystkich konfiguracji odbywa się na podstawie dużej bazy danych gier rozgrywanych między silnymi graczami i obliczania statystyk dla każdej konfiguracji na każdym etapie gry ze wszystkich gier.

Najczęstszym wyborem do przewidywania ostatecznej różnicy dysków jest miara ważonej różnicy dysków, w której zwycięska strona otrzymuje premię odpowiadającą liczbie dysków.

Otwarcie książki

Otwieranie książek pomaga programom komputerowym, dając wspólne otwarcia, które są uważane za dobre sposoby przeciwdziałania słabym otwarciom. Wszystkie silne programy używają otwierania książek i aktualizują je automatycznie po każdej grze. Aby przejrzeć wszystkie pozycje ze wszystkich gier w bazie danych gier i określić najlepszy ruch, który nie został wykonany w żadnej grze w bazie danych, tabele transpozycji do zapisywania pozycji, które zostały wcześniej wyszukane. Oznacza to, że tych pozycji nie trzeba ponownie wyszukiwać. 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żdej rozegranej grze wszystkie nowe pozycje są wyszukiwane pod kątem najlepszego odchylenia.

Inne optymalizacje

Szybszy sprzęt i dodatkowe procesory mogą poprawić możliwości programów odtwarzających Othello, takie jak głębsze wyszukiwanie warstw.

Rozwiązywanie Othello

Podczas rozgrywki gracze naprzemiennie poruszają się. Gracz-człowiek używa czarnych żetonów, podczas gdy komputer używa białych. Gracz będący człowiekiem rozpoczyna grę. Othello jest mocno rozwiązany na planszach 4 × 4 i 6 × 6, przy czym drugi gracz (biały) wygrywa w doskonałej grze . Pozostaje nierozwiązany na standardowej planszy 8 × 8, ale analiza komputerowa daje tysiące losowania lub ścieżek do remisu, 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 mniej niż jedną sekundę przez wiele prostych programów Othello, które wykorzystują 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 mniej niż 100 godzin za pomocą wielu prostych programów Othello, które wykorzystują metodę Minimax, która generuje wszystkie możliwe pozycje (prawie 3,6 biliona). W rezultacie białe wygrywają z przewagą +4 (16-20).

Otello 8 × 8

Rozmiar drzewa gry Othello 8x8 szacuje się na 10 ⁵⁴ węzłów, a liczbę legalnych pozycji szacuje się na mniej niż 10 ²⁸ . Gra pozostaje nierozwiązana. Rozwiązanie można by prawdopodobnie znaleźć przy użyciu 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 którejkolwiek ze stron. Jeśli chodzi o trzy główne otwory ukośne, prostopadłe i równoległe, wydaje się, że zarówno otwory ukośne, jak i prostopadłe 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, umożliwiając czarnym zawsze wygrywać w idealnej grze.

Kamienie milowe w komputerze Othello


	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 (4. mecz)

1977 : Scientific American opublikował najwcześniejszą znaną wzmiankę o programie Othello/Reversi, napisanym przez NJD Jacobsa w BCPL . Firma BYTE opublikowała w październiku „Othello, a New Ancient Game” jako program do pisania w języku BASIC .
1977 : Creative Computing opublikowało wersję Othello napisaną przez Eda Wrighta w języku FORTRAN .
1978 : Nintendo wypuszcza grę wideo Computer Othello w salonach gier .
1980 : Program Othello The Moor (napisany przez Mike'a Reeve'a i Davida Levy'ego ) wygrał jedną grę w meczu składającym się z sześciu gier z mistrzem świata Hiroshi Inoue. Peter W Frey z Northwestern University omówił komputerowe i ludzkie strategie Othello w BYTE i omówił 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 stworzył IAGO , który zajął trzecie miejsce w turnieju komputerowym Northwestern University. Kiedy IAGO grało z Wrzosowiskiem, IAGO lepiej radziło sobie z trwałym przebijaniem figur i ograniczaniem mobilności przeciwnika.
1981 : IAGO biegnąc na DEC KA10 ukończyło przed 19 innymi zawodnikami Otwarty Turniej Othello w Santa Cruz 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 zajęły miejsca od drugiego do siódmego, wyprzedzając kilka komputerów typu mainframe i minikomputerów; Frey spekulował, że dzieje się tak, ponieważ komputer Othello nie korzysta z kilku zalet większych komputerów, takich jak szybsza arytmetyka zmiennoprzecinkowa .
Późne lata 80 .: 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 Othello Logistello . Techniki wyszukiwania Logistello, funkcja oceny i baza wiedzy o wzorcach były lepsze niż we wcześniejszych programach. Logistello udoskonalił swoją grę, rozgrywając przeciwko sobie ponad 100 000 gier.
1997 : Logistello wygrał wszystkie mecze w sześciu meczach z mistrzem świata Takeshim Murakamim. Chociaż nie było większych wątpliwości, że programy Othello są silniejsze od ludzi, minęło 17 lat od ostatniego meczu między komputerem a aktualnym mistrzem świata. Po meczu z 1997 roku nie było już żadnych wątpliwości: Logistello był znacznie lepszy niż jakikolwiek ludzki gracz.
1998 : Michael Buro przechodzi na emeryturę z 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 stały się znacznie silniejsze niż Logistello. Ntest i Zebra przeszły na emeryturę.
2011 : Saio , Edax i Cyrano stały się znacznie szybsze niż Logistello i inne programy.

Lista najlepszych programów Othello/Reversi

NTest ( Ntest ) autorstwa Chrisa Welty'ego
Edax ( Edax ) autorstwa Richarda Delorme
Logistello autorstwa Michaela Buro

Zobacz też

Notatki

Linki zewnętrzne

Computer Othello

NTest - silny program othello