Стабло игре
У контексту комбинаторне теорије игара, која обично проучава секвенцијалне игре са савршеним информацијама, стабло игре је граф који представља сва могућа стања игре унутар такве игре. Такве игре укључују неке од добро познатих као што су шах, даме, го и тик-так-тое. Ово се може користити за мерење сложености игре, јер представља све могуће начине на које игра може да се одигра. Због великог стабла игара сложених игара као што је шах, алгоритми који су дизајнирани да играју ову класу игара користиће делимична стабла игара, што чини израчунавање изводљивим на савременим рачунарима. Постоје различите методе за решавање стабала игре. Ако се може генерисати комплетно стабло игре, може се користити детерминистички алгоритам, као што је индукција уназад или ретроградна анализа. Рандомизовани алгоритми и минмак алгоритми као што је МЦТС могу се користити у случајевима када комплетно стабло игре није изводљиво.
Разумевање стабла игре уреди
Да би се боље разумело стабло игре, оно се може сматрати техником за анализу супарничких игара, које одређују радње које играч предузима да би победио у игри. У теорији игара, дрво игре је усмерен граф чији су чворови позиције у игри (нпр. распоред фигура у игри на плочи) и чије су ивице потези (нпр. за померање делова са једне позиције на табли на другу).[1]
Комплетно стабло игре је стабло игре које почиње на почетној позицији и садржи све могуће потезе са сваке позиције; комплетно стабло је исто дрво као оно добијено из екстензивног приказа игре. Прецизније, комплетна игра је норма за игру у теорији игара. Што може јасно изразити многе важне аспекте. На пример, редослед акција које заинтересоване стране могу да предузму, њихов избор у свакој тачки одлучивања, информације о радњама које су предузеле друге заинтересоване стране када свака заинтересована страна доноси одлуку и користи од свих могућих резултата игре.[2]
Референце уреди
- ^ Зуцкерман, Инон; Wилсон, Брандон; Нау, Дана С. (2018). „Авоидинг гаме-трее патхологy ин 2-плаyер адверсариал сеарцх”. Цомпутатионал Интеллигенце (на језику: енглески). 34 (2): 542—561. ИССН 1467-8640. С2ЦИД 46926187. дои:10.1111/цоин.12162.
- ^ Хуанг, Зисхуо; Yу, Ханг; Цху, Xиангyанг; Пенг, Зхенwеи (2018-05-01). „А новел оптимизатион модел басед он гаме трее фор мулти-енергy цонверсион сyстемс”. Енергy (на језику: енглески). 150: 109—121. ИССН 0360-5442. дои:10.1016/ј.енергy.2018.02.091.
Литература уреди
- Ху, Те Цхианг; Схинг, Ман-так (2002). Цомбинаториал Алгоритхмс. Цоуриер Довер Публицатионс. ИСБН 0-486-41962-2. Приступљено 2007-04-02.
- Јудеа Пеарл, Хеуристицс, Аддисон-Wеслеy, 1984