TD-Gammon - TD-Gammon

TD-Gammon to komputerowy program do gry w backgammon opracowany w 1992 roku przez Geralda Tesauro w IBM 's Thomas J. Watson Research Center . Jego nazwa pochodzi od faktu, że jest to sztuczna sieć neuronowa trenowana przez formę uczenia się różnic czasowych , a konkretnie TD-lambda .

TD-Gammon osiągnął poziom gry nieco poniżej poziomu najlepszych graczy tamtych czasów. Zbadano strategie, do których ludzie nie dążyli, i doprowadziły do ​​postępów w teorii poprawnej gry w tryktraka.

Algorytm do zabawy i nauki

Podczas gry TD-Gammon sprawdza w każdej turze wszystkie możliwe legalne ruchy i wszystkie ich możliwe odpowiedzi ( dwuwarstwowe spojrzenie w przód ), przekazuje każdą wynikową pozycję na planszy do swojej funkcji oceny i wybiera ruch, który prowadzi do pozycji na szachownicy, która uzyskała najwyższą wynik. Pod tym względem TD-Gammon nie różni się od prawie wszystkich innych komputerowych gier planszowych. Innowacja TD-Gammon polegała na tym, jak nauczył się swojej funkcji oceny.

Algorytm uczenia TD-Gammona polega na uaktualnianiu wag w sieci neuronowej po każdej turze, aby zmniejszyć różnicę między oceną pozycji planszy w poprzednich turach a oceną pozycji planszy w obecnej turze - stąd „ uczenie się różnic czasowych ”. Wynik dowolnej pozycji na szachownicy to zestaw czterech liczb odzwierciedlających oszacowanie przez program prawdopodobieństwa każdego możliwego wyniku gry: białe wygrywają normalnie, czarne wygrywają normalnie, białe wygrywają baleron, czarne wygrywają baleron. W przypadku ostatecznej pozycji na szachownicy algorytm porównuje się z rzeczywistym wynikiem gry, a nie z własną oceną pozycji na szachownicy.

Po każdej turze algorytm uczący się aktualizuje każdą wagę w sieci neuronowej zgodnie z następującą zasadą:

${\ Displaystyle w_ {t + 1} -w_ {t} = \ alfa (Y_ {t + 1} -Y_ {t}) \ suma _ {k = 1} ^ {t} \ lambda ^ {tk} \ nabla _ {w} Y_ {k}}$

gdzie:

${\ displaystyle w_ {t + 1} -w_ {t}}$	jest kwotą zmiany wagi w stosunku do jej wartości w poprzedniej turze.
${\ Displaystyle Y_ {t + 1} -Y_ {t}}$	jest różnicą między ocenami na planszy w bieżącej i poprzedniej turze.
${\ displaystyle \ alpha}$	jest parametrem „ szybkości uczenia się ”.
${\ displaystyle \ lambda}$	to parametr, który wpływa na to, jak bardzo obecna różnica w ocenach tablicy powinna się zwrócić do poprzednich szacunków. sprawia, że ​​program koryguje tylko oszacowanie z poprzedniej tury; powoduje, że program próbuje skorygować oszacowania na wszystkich poprzednich turach; a wartości od 0 do 1 określają różne szybkości, przy których znaczenie starszych oszacowań powinno „zanikać” w czasie. ${\ displaystyle \ lambda = 0}$${\ displaystyle \ lambda = 1}$${\ displaystyle \ lambda}$
${\ displaystyle \ nabla _ {w} Y_ {k}}$	jest gradientem wyjścia sieci neuronowej w odniesieniu do wag: to znaczy, ile zmiana wagi wpływa na wynik.

Eksperymenty i etapy treningu

W przeciwieństwie do poprzednich programów do tryktraka sieci neuronowych, takich jak Neurogammon (również napisany przez Tesauro), gdzie ekspert szkolił program, dostarczając „poprawną” ocenę każdej pozycji, TD-Gammon był początkowo zaprogramowany jako „wolny od wiedzy”. We wczesnych eksperymentach, wykorzystując tylko surowe kodowanie planszowe bez funkcji zaprojektowanych przez człowieka, TD-Gammon osiągnął poziom gry porównywalny z Neurogammon: gracz na średnim poziomie ludzkim backgammon.

Mimo że TD-Gammon sam odkrył wnikliwe funkcje, Tesauro zastanawiał się, czy jego grę można poprawić, używając ręcznie zaprojektowanych funkcji, takich jak Neurogammon. Rzeczywiście, samouczący się TD-Gammon z funkcjami zaprojektowanymi przez ekspertów wkrótce przewyższył wszystkie poprzednie programy komputerowe do backgammona. Przestał się poprawiać po około 1500000 gier (gra samodzielna) przy użyciu 80 ukrytych jednostek.

Postępy w teorii backgammona

Ekskluzywny trening TD-Gammona poprzez grę samodzielną (a nie opiekę) umożliwił mu zbadanie strategii, których ludzie wcześniej nie brali pod uwagę lub błędnie wykluczyli. Jej sukces dzięki niekonwencjonalnym strategiom miał znaczący wpływ na społeczność backgammona.

Na przykład w grze otwierającej konwencjonalną mądrością było to, że przy wyrzucie 2-1, 4-1 lub 5-1 białe powinny przesunąć pojedynczy pionek z punktu 6 do punktu 5. Znany jako „szczelina”, to technika zamienia ryzyko trafienia na możliwość zajęcia agresywnej pozycji. TD-Gammon stwierdził, że bardziej konserwatywna gra 24-23 była lepsza. Gracze turniejowi zaczęli eksperymentować z ruchem TD-Gammona i odnieśli sukces. W ciągu kilku lat automaty zniknęły z gry turniejowej. (Jednak teraz pojawia się ponownie dla 2-1.)

Ekspert w backgammon, Kit Woolsey, stwierdził, że ocena pozycji TD-Gammona, a zwłaszcza ocena ryzyka w stosunku do bezpieczeństwa, była lepsza od oceny jego własnej lub jakiegokolwiek człowieka.

Doskonała gra pozycyjna TD-Gammona była podważana przez sporadyczne słabą grę końcową. Końcówka wymaga bardziej analitycznego podejścia, czasem z rozbudowanym wyprzedzeniem. Ograniczenie TD-Gammon do dwuwarstwowego spojrzenia naprzód kładzie pułap na tym, co można osiągnąć w tej części gry. Mocne i słabe strony TD-Gammon były przeciwieństwem symbolicznych programów sztucznej inteligencji i większości programów komputerowych w ogóle: był dobry w sprawach wymagających intuicyjnego „wyczucia”, ale źle radził sobie z systematyczną analizą.

Bibliografia