Różnice między wybraną wersją a wersją aktualną.
| Both sides previous revision Poprzednia wersja Nowa wersja | Poprzednia wersja | ||
|
pl:dydaktyka:ggp:mcts [2016/05/18 08:59] msl [Monte Carlo Tree Search] |
pl:dydaktyka:ggp:mcts [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 50: | Linia 50: | ||
| Algorytm można podzielić na cztery fazy: | Algorytm można podzielić na cztery fazy: | ||
| - | - wybór: wszystkie możliwe ruch z przeszukiwanego węzła mają policzone statystyki (już kiedyś był zagrany) używamy formuły UCT, aby wybrać ruch. Powtarzamy to tak długo jak możemy na kolejnych węzłach. | + | - wybór: jeżeli wszystkie możliwe ruchy z przeszukiwanego węzła mają policzone statystyki (każdy już kiedyś był zagrany) używamy formuły UCT, aby wybrać ruch. Jeśli nie, przechodzimy do fazy rozrostu. |
| * :!: **UWAGA** :!: podobnie jak w algorytmie MiniMax zakładamy, że na przemian wykonywane są ruchy nasze i wroga. Jeżeli wróg wykonuje ruch, stara się maksymalizować swoje wyniki (lub minimalizować nasze, co jest tożsame w przypadku gier o sumie zerowej). Zatem, albo modyfikujemy formułę UCT, np. : $(1 - \overline{wynik_i}) + c*\sqrt{{n}\over{n_i}}$, albo odpowiednio zapisujemy wyniki. | * :!: **UWAGA** :!: podobnie jak w algorytmie MiniMax zakładamy, że na przemian wykonywane są ruchy nasze i wroga. Jeżeli wróg wykonuje ruch, stara się maksymalizować swoje wyniki (lub minimalizować nasze, co jest tożsame w przypadku gier o sumie zerowej). Zatem, albo modyfikujemy formułę UCT, np. : $(1 - \overline{wynik_i}) + c*\sqrt{{n}\over{n_i}}$, albo odpowiednio zapisujemy wyniki. | ||
| - | - rozrost: jeżeli żaden ruch z danego węzła nie był nigdy grany, wybieramy losowy ruch. | + | - rozrost: jeżeli żaden ruch z danego węzła nie był nigdy grany, wybieramy losowy jeszcze niegrany ruch. |
| - symulacja: z węzła wybranego w fazie rozrostu, przeprowadzamy losową symulację Monte Carlo | - symulacja: z węzła wybranego w fazie rozrostu, przeprowadzamy losową symulację Monte Carlo | ||
| - | - propagacja wyników wstecz: po wygranej lub przegranej, odpowiednio aktualizujemy statystyki odpowiednich ruchów | + | - propagacja wyników wstecz: po wygranej lub przegranej, odpowiednio aktualizujemy statystyki odpowiednich ruchów (nie obejmuje to ruchów wykonanych w ramach symulacji). |
| {{ :pl:dydaktyka:ggp:mcts-fazy.png?700 |}} | {{ :pl:dydaktyka:ggp:mcts-fazy.png?700 |}} | ||
