Monte Carlo z UCB zastosowane do złożonej gry karcianej

Question

Próbuję zrozumieć, jak działa algorytm MCTS i jak zaimplementować go w grze karcianej, aby ulepszyć silnik AI.

Przeczytałem stronę internetową mcts.ai/ oraz wiele artykułów na ten temat, w tym jedną, która pokazuje pewne wyniki dotyczące powodzenia stosowania Monte Carlo Search z UCB w AI dla gry w karty Magic, czyli mniej więcej co Muszę to zrobić, ale mam problem ze zrozumieniem niektórych punktów i jak je zastosować, aby rozwiązać to, czego potrzebuję. Nie mam zbyt dużego doświadczenia w matematyce, więc gubię się, gdy dokumenty tłumaczą to wszystko skomplikowanymi formułami.

To co ja wymyślił do tej pory:

1. Biorąc pod uwagę stan gry (ręka użytkownika w grze), określić, które są wszystkie możliwe odtworzeń prawne, które mogą być wykonane to bym utworzyć listę węzłów (jeden reprezentujący każde odtworzenie) jako właściwość w głównym węźle MCTSTree z wynikiem każdego z nich (wartość wyniku?)

2. Symulacja kompletnej (do końca) rozgrywki dla każdej z tych legalnych gier z losowy gracz i zapisuje wynik w każdym węźle, niezależnie od tego, czy gracz wygrał, czy przegrał, aby mieć pełny obraz.

Oto gdzie „myślę” Monte Carlo + UCB powinny być stosowane:

1. Wybierz bardziej obiecującą grę (węzeł) używając UCB rekurencyjnie aw przypadku jego liści, poszerzyć ten węzeł z wszystkie możliwe gry ze swojego gameState.

2. Symulacja n odtwarzań z wybranego węzła, aż do osiągnięcia określonego czasu.

   • Na tym etapie mam pewne wątpliwości ... mówię, że próbuję losowego playoutu z podaniem listy możliwych rozgrywek ... co mam zrobić z tym pierwszym wynikiem, aby kontynuować symulację? Czy powinnam sprawić, aby drzewo rosło?

3. Jak mogę cofnąć poprawność wyników?

Następnie

• Mając na uwadze, że jest to złożona gra karty i mam tak wiele możliwych ruchów ... Czy to ma dobrą wydajność, wystarczy, że tak wielu Childs w dowolnym węźle?

• Jeśli każda symulacja jest oparta na gamestacie, a gra zmienia stan za każdym razem, gdy gracz stosuje ruch, to skąd mogę wiedzieć, czy drzewo jest naprawdę przydatne?

Byłbym wdzięczny za pomoc w tej sprawie.

Dziękuję bardzo!

Answer 1

MCTS jest tylko następujące:

opiszę to nieco inaczej niż to, co sugeruje, że obraz, który mógłby być bardziej gotowy do realizacji.

1. Descent od węzła głównego (aktualny stan gry), stosując UCB na każdym kroku aż decydować uninstantiated węzeł l. (Wybierz)
2. Dodaj l do drzewa. (Rozwiń)
3. Od l, graj w losową grę. (Symulacja)
4. Zaktualizuj wszystkie węzły na ścieżce od l z powrotem do węzła głównego z wynikiem odtworzenia.
5. Powtarzaj, aż skończy się czas.

Jeśli twój czynnik rozgałęziania jest duży, jak wspomniano, być może trzeba będzie rozważyć inne strategie wyboru następcy podczas zstępowania drzewa, takie jak RAVE.