Jak korzystać ze sztucznej inteligencji w szachach komputerowych

W niektórych (historycznych) artykułach szachy określane są mianem drozofili sztucznej inteligencji. Chociaż przypuszczam, że w bieżących badaniach zwykłe zastosowanie algorytmu wyszukiwania jest w najlepszym przypadku zaawansowaną informatyką , uważam, że nadal istnieją obszary, w których można zastosować (i ćwiczyć) techniki sztucznej inteligencji.

Prostym przykładem może być uczenie się na podstawie książki otwierającej, w której można nauczyć program, czy ma używać pewnych ruchów w otworze, ponieważ program nie jest przystosowany do określonych typów pozycji. Możemy użyć formy uczenia się na nowo i zautomatyzować to: Przypuszczam, że mógłbym grać w program przeciwko sobie i zwiększyć prawdopodobieństwo wygranych linii i zmniejszyć prawdopodobieństwo utraty linii.

Bardziej złożonym przykładem jest użycie funkcji oceny uczenia się (na przykład można poprawić wartości tabel kwadratowych ). Myślę jednak:

biorąc pod uwagę cały hałas spowodowany ogromną ilością realistycznych pozycji (w przeciwieństwie do ilości realistycznych linii początkowych)
oraz kosztem (czasem trwania) szachowej gry komputerowej i koniecznością grania.

Jak można to zrobić skutecznie? (lub powinienem spojrzeć na inne techniki, na przykład sieci neuronowe).

artificial-intelligence board-games

— ljgw
źródło

Standardowym podejściem jest przycięta minimax alfa-beta. z heurystyką. Pochodzi z rodziny AI wyszukiwania, a nie z rodziny uczącej się maszynowo.

— Lyndon White

Właściwi mistrzowie szachowi po prostu pamiętają wszystkie gry, w które wcześniej grali ... Więc mają mocne zapamiętywanie.

Istnieje również roszczenie wzajemne. Nie pamiętam, kto to powiedział, ale tak to wygląda. Biolodzy wykorzystują eksperymenty na drozofilach, aby uzyskać coraz głębsze zrozumienie fizjologii, genetyki i tak dalej. Ludzie AI piszą na szachach, aby coraz lepiej grać w szachy. To niewiele nas uczy o informatyce; to tak, jakby biolodzy hodowali superszybką, supersilną drozofilę i zmuszali ich do walki.

— David Richerby

jak mówi metafora, jest możliwe, że jest to coś więcej niż „drozofila sztucznej inteligencji”, ale różne aspekty, szczególnie biorąc pod uwagę, że nie pokonała ona zdecydowanie czołowego człowieka aż do ~ 1997 r., a badania nad nią trwają itp.

— wer

Odpowiedzi:

Cała przestrzeń dla szachów jest ogromna - można ją z grubsza oszacować na 10 ⁴³ (liczba Shannona (Shannon, 1950) , ( Wikipedia )).

Przedstawiony przez Ciebie pomysł - agenci Reinforcement Learning, którzy grają ze sobą, aby nauczyć się gry - został pomyślnie zastosowany w grze Backgammon - TD-Gammon (Tesauro, 1995) , ( Rozdział w Reinforcement Learning autorstwa Sutton & Barto ). Wykorzystał także sieci neuronowe do oszacowania funkcji wartości gry. Problem ten jest jednak o wiele prostszy, ponieważ liczba stanów w grze Backgammon jest znacznie mniejsza niż w szachach, a mianowicie: 18 528 584, 051,601,162,496 ( wątek Archiwum forum gry Backgammon ).

Jeśli jednak zakończyłbyś grę po kilku początkowych ruchach i dążysz tylko do nauczenia się „dobrych otworów”, możesz odnieść sukces dzięki analogicznemu podejściu. Głównym problemem będzie ocena gry po grze otwierającej, co wydaje się trudne. Samo podobieństwo do ustalonych pozycji po dobrze znanych otwarciach nie jest wystarczające, ponieważ pozycja może być daleko od nich, jeśli przeciwnik wykonałby głupi ruch (więc nie byłoby tak z powodu błędu agenta uczącego się, więc pozycja nawet jeśli „niepoprawna” „należy ocenić jako dobry wynik).

Bibliografia:

— BartoszKP
źródło

Rzeczywiście najtrudniejsza jest wymyślenie empirycznego sposobu na zdobycie wyniku otwarć. Różne otwory są dobre na różne sposoby, więc prawdopodobnie istnieje wiele dopuszczalnych otworów.

— JDong

Jestem prawie pewien, że jakakolwiek możliwa (lub dziwna) metoda AI lub ML w podręcznikach została wypróbowana i prawie nieudana w porównaniu z prostą brutalną siłą.

Moim osobistym punktem widzenia jest to, że szachy same w sobie nie są już zainteresowane nowoczesną sztuczną inteligencją ... Po prostu dlatego, że można je rozwiązać : po prostu używając nowoczesnego komputera i brutalnej siły. Nie uważam więc, że istnieje potrzeba stworzenia „inteligentnego” systemu, aby rozwiązać go bardziej efektywnie (działa dobrze w moim telefonie komórkowym) i uważam, że nie ma nawet potrzeby czegoś nieznanego i więcej „inteligentne” podejście do istnienia.

— iliasfl
źródło

Nie jestem pewien, dlaczego to zostało odrzucone. Argument, że szachy są „rozwiązane”, jest nieco niedokładny, ponieważ żaden komputer nie jest w stanie spojrzeć na żadną możliwą pozycję i perfekcyjnie ją ocenić. To powiedziawszy, iliasfl jest na miejscu, że szachy straciły większość swojego zainteresowania badaniami nad AI. Po pierwsze, najlepsze komputerowe programy szachowe są teraz znacznie silniejsze niż najlepsi ludzie, biorąc pod uwagę wystarczającą moc obliczeniową i czas. To sprawia, że programistom coraz trudniej jest nawet ocenić, jak dobrze działa algorytm.

— elixenide

Dzięki, powiedziałem rozwiązany w tym sensie, że brutalna siła jest rozwiązaniem. Oczywiście społeczność AI (ogólnie nie tylko tutaj) nie jest zadowolona z tego „rozwiązania”. Jednak mamy już system obliczeniowy, który prezentuje „inteligentne” zachowanie w celu rozwiązania tego zadania, a nawet wygrania najlepszych ludzi, kropka. Osobiście uważam, że szachy będą nie na temat AI po kilku latach, kiedy obecna masa naukowców, którzy spędzili karierę, atakując ją, odejdzie na emeryturę.

Nie nazwałbym obecnych implementacji szachów komputerowych „rozwiązanymi przez brutalną siłę” - wciąż szukają ogromnych ilości gamestatów, ale jest tam wiele elementów nie-brutalnej siły. Oczywiście nie są to rozwiązania w „ludzkim stylu”, które dobrze uogólniłyby inne problemy, ale nie zdziwiłbym się, gdybyśmy mieli sztuczną inteligencję szachową w „ludzkim stylu”, byłoby to o wiele rzędów wielkości mniej wydajne niż obecne specjalistyczne rozwiązania, co czyni go po prostu gorszym.

— Peteris

Myślę, że ta odpowiedź i jej komentarze zostały dość wyraźnie obalone przez Google AlphaZero: en.wikipedia.org/wiki/AlphaZero Nawet jeśli zaakceptujesz krytykę dotyczącą konfiguracji Sztokfiszka i narysowali wszystkie mecze, system, który osiągnął ten poziom z kilkoma godzinami treningu jest wyraźnie lepszy.

— Kamal

Myślę, że warto zauważyć, że aby określić sposób rozwiązania problemu sztucznej inteligencji, musisz go zdefiniować. Czy jest to w pełni obserwowalne lub częściowo obserwowalne oraz czy jest deterministyczne czy stochastyczne / przypadkowe.

Chess jest w pełni przestrzegana, (w przeciwieństwie do backgammon, monopol lub pokera na przykład) Jest również deterministyczny (jak warcaby, i idź na przykład) Wreszcie istnieją przeciwnicy i dlatego przy określaniu następny najlepszy ruch warto używać kontradyktoryjności Search typ algorytmy takie jak MiniMax. Klasyfikacja problemu może pomóc nam ustalić, jakiego rodzaju algorytmu wyszukiwania chcielibyśmy zastosować. W przypadku szachów Poszukiwanie Przeciwne byłoby odpowiednie.

W szczególności minimax ma

$O(b^n)$

$O(bm)$

W przypadku szachów b wynosi 35, a m 100. Istnieją sposoby lub strategie zwiększania wydajności, takie jak odcięcie alfa-beta.

— Iancovici
źródło

Warto również zauważyć w tym kontekście, że końcowe gry w szachy dla kilku sztuk są już zestawione w tabeli - dalsza optymalizacja.

— BartoszKP

Jest to normalne podejście, ale nie podejście oparte na uczeniu maszynowym. Pytanie wykorzystuje tag uczenia maszynowego.

— Lyndon White

@Oxinabox, chociaż było to prawdą, pytający nie wspomniał, gdzie w tytule lub treści interesuje się podejściem uczenia maszynowego, tylko na końcu, gdzie podzielił się jednym przykładem podejścia, które miał na myśli. Nie ma potrzeby ograniczania problemu do uczenia maszynowego ani pojedynczego algorytmu uczenia się (NN).

— Iancovici

Rzeczywiście to jest dobre

— Lyndon White

ściślej mówiąc, szachy nie są w pełni obserwowalne, ponieważ na przykład nie wiemy, czy król lub wieża już się poruszył, czy nie, choć jest to ważne dla generowania ruchów (czy castling jest nadal możliwy?), ale programista może uczynić go w pełni obserwowalnym, zmieniając reprezentację pozycji, rozróżniając nieruchome króla / wieżę i ruszonego króla / wieżę jako różne figury, choć powoduje to pewne trudności.