TD-Gammon

TD-Gammon to komputerowy program do tryktraka opracowany w 1992 roku przez Geralda Tesauro w Centrum Badawczym IBM Thomas J. Watson . Jego nazwa pochodzi od faktu, że jest to sztuczna sieć neuronowa trenowana przez formę uczenia się różnic czasowych , w szczególności TD-Lambda .

TD-Gammon osiągnął poziom gry nieco niższy od najlepszych graczy w tryktrak w tamtych czasach. Zbadano strategie, których ludzie nie stosowali, i doprowadziło do postępu w teorii prawidłowej 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 (podwójne wyprzedzanie ) , wprowadza każdą wynikową pozycję na szachownicy 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ę niczym od niemal każdego innego programu komputerowego do gier planszowych. Innowacja TD-Gammon polegała na tym, jak nauczył się swojej funkcji oceny.

Algorytm uczenia TD-Gammon polega na aktualizowaniu wag w jego sieci neuronowej po każdej turze w celu zmniejszenia różnicy 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 oszacowane przez program prawdopodobieństwo każdego możliwego wyniku gry: białe wygrywa normalnie, czarne wygrywa normalnie, białe wygrywa baleron, czarne wygrywa baleron. Dla ostatecznej pozycji na szachownicy gry algorytm porównuje raczej z faktycznym wynikiem gry niż z własną oceną pozycji na szachownicy.

Po każdym turze algorytm uczący aktualizuje każdą wagę w sieci neuronowej zgodnie z następującą regułą:

${\ 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}}$	to kwota, o jaką należy zmienić wagę w porównaniu z jej wartością z poprzedniej tury.
${\ Displaystyle Y_ {t + 1} - Y_ {t}}$	to różnica między ocenami planszy bieżącej i poprzedniej tury.
${\ Displaystyle \ alfa}$	jest parametrem „ szybkości uczenia się ”.
${\ Displaystyle \ lambda}$	jest parametrem, który wpływa na to, w jakim stopniu obecna różnica w ocenach zarządu powinna być sprzężona z poprzednimi szacunkami. ${\ displaystyle \ lambda = 0}$ powoduje, że program poprawia tylko oszacowanie poprzedniego zwrotu; ${\ displaystyle \ lambda = 1}$ powoduje, że program próbuje poprawić szacunki we wszystkich poprzednich turach; a wartości $1$ określają różne szybkości, z jakimi znaczenie starszych szacunków powinno „zanikać” w czasie
${\ Displaystyle \ nabla _ {w} Y_ {k}}$	to gradient danych wyjściowych sieci neuronowej w odniesieniu do wag: to znaczy, jak bardzo zmiana wagi wpływa na dane wyjściowe.

Eksperymenty i etapy szkolenia

W przeciwieństwie do poprzednich programów backgammon z siecią neuronową, takich jak Neurogammon (również napisany przez Tesauro), w których ekspert szkolił program, dostarczając „poprawną” ocenę każdej pozycji, TD-Gammon był początkowo zaprogramowany „bez wiedzy”. We wczesnych eksperymentach, używając tylko surowego kodowania planszy bez funkcji zaprojektowanych przez człowieka, TD-Gammon osiągnął poziom gry porównywalny z Neurogammon: poziom średniozaawansowanego gracza w tryktraka.

Mimo że TD-Gammon samodzielnie odkrył wiele ciekawych funkcji, Tesauro zastanawiał się, czy jego grę można ulepszyć, 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 komputerowe programy do tryktraka. Przestał się poprawiać po około 1 500 000 gier (gra samodzielna) przy użyciu 80 ukrytych jednostek.

Postępy w teorii tryktraka

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

Na przykład w grze otwierającej konwencjonalna mądrość była taka, że ​​​​przy rzucie 2-1, 4-1 lub 5-1 białe powinny przesunąć pojedynczy pionek z punktu 6 do punktu 5. Znany jako „slotting”, ten technika zamienia ryzyko trafienia na możliwość rozwinięcia agresywnej pozycji. TD-Gammon stwierdził, że bardziej zachowawcza gra 24-23 była lepsza. Gracze turniejowi zaczęli eksperymentować z ruchem TD-Gammon i odnieśli sukces. W ciągu kilku lat sloty zniknęły z rozgrywek turniejowych, ale w 2006 roku pojawiły się ponownie, wygrywając 2-1.

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

Doskonała gra pozycyjna TD-Gammon była podkopywana przez sporadyczne słabe gry końcowe. Gra końcowa wymaga bardziej analitycznego podejścia, czasami z obszernym spojrzeniem w przyszłość. Ograniczenie TD-Gammon do dwuwarstwowego lookahead wyznacza pułap tego, co może osiągnąć w tej części gry. Mocne i słabe strony TD-Gammon były przeciwieństwem symbolicznych programów sztucznej inteligencji i ogólnie większości programów komputerowych: był dobry w sprawach wymagających intuicyjnego „wyczucia”, ale kiepski w systematycznej analizie.

Zobacz też

• Światowa Federacja Backgammon

Linki zewnętrzne

• TD-Gammon w IBM
• TD-Gammon na GitHubie