Logo-semin

SEMINARIUM NAUKOWE
Grafika komputerowa,
przetwarzanie i rozpoznawanie obrazów

 Streszczenie

mgr inż. LESZEK ŚLIWA
Instytut Informatyki Politechnika Warszawska

Zastosowanie wzorców w programie komputerowym do gry w Go

Tematem prezentacji jest budowa heurystyki bazującej na wzorcach i jej zastosowanie w programie komputerowym do gry w Go. Zbudowanie dobrej heurystyki dla gry w Go jest trudne. Drzewo gry jest silnie rozgałęzione i powstaje obawa, że heurystyka może eliminować silne zagrania. Jednym z pomysłów na zbudowanie heurystyki jest użycie bazy „dobrych” wzorców. Najczęściej wzorzec jest fragmentem planszy o rozmiarze 3x3 z zaznaczonymi punktami wolnymi i punktami zajmowanymi przez kamienie czarne lub białe. Każdemu potencjalnemu ruchowi, wykonywanemu w centralnym punkcie wzorca, przypisana jest waga. Heurystyka wybiera ruch odpowiadający wzorcowi mającemu największą wagę. Baza wzorców może być opracowana przez eksperta lub pozyskana na drodze maszynowego uczenia. W prezentacji pokazano metodę maszynowego pozyskania bazy wzorców na podstawie zapisów gier rozegranych pomiędzy ludzkimi graczami.

W ostatnich latach został opracowany nowy algorytm MCTS (ang. Monte Carlo Tree Search). Metoda MCTS skupia się na analizie najbardziej obiecujących ruchów, w której rozrost drzewa wariantów bazuje na losowym próbkowaniu przestrzeni przeszukiwań. Zastosowanie metody MCTS w programach komputerowych do gry w Go, zbliżyło ich siłę gry do poziomu mistrzowskiego. Algorytm MCTS w podstawowej wersji nie bazuje na wiedzy eksperckiej i znajduje zastosowanie także w innych dziedzinach.

W prezentacji pokazano sposób maszynowego pozyskania bazy wzorców, implementację w programie komputerowym do gry w Go i metodę weryfikacji wpływu heurystyki na siłę gry programu. Zaprezentowano i omówiono wyniki przeprowadzonych eksperymentów.


 


Stronę opracował C. Stępień
Ostatnia modyfikacja 05 grudnia 2014