Stablo igre

U kontekstu kombinatorne teorije igara, koja obično proučava sekvencijalne igre sa savršenim informacijama, stablo igre je graf koji predstavlja sva moguća stanja igre unutar takve igre. Takve igre uključuju neke od dobro poznatih kao što su šah, dame, go i tik-tak-toe. Ovo se može koristiti za merenje složenosti igre, jer predstavlja sve moguće načine na koje igra može da se odigra. Zbog velikog stabla igara složenih igara kao što je šah, algoritmi koji su dizajnirani da igraju ovu klasu igara koristiće delimična stabla igara, što čini izračunavanje izvodljivim na savremenim računarima. Postoje različite metode za rešavanje stabala igre. Ako se može generisati kompletno stablo igre, može se koristiti deterministički algoritam, kao što je indukcija unazad ili retrogradna analiza. Randomizovani algoritmi i minmak algoritmi kao što je MCTS mogu se koristiti u slučajevima kada kompletno stablo igre nije izvodljivo.

Razumevanje stabla igre

Da bi se bolje razumelo stablo igre, ono se može smatrati tehnikom za analizu suparničkih igara, koje određuju radnje koje igrač preduzima da bi pobedio u igri. U teoriji igara, drvo igre je usmeren graf čiji su čvorovi pozicije u igri (npr. raspored figura u igri na ploči) i čije su ivice potezi (npr. za pomeranje delova sa jedne pozicije na tabli na drugu).^[1]

Kompletno stablo igre je stablo igre koje počinje na početnoj poziciji i sadrži sve moguće poteze sa svake pozicije; kompletno stablo je isto drvo kao ono dobijeno iz ekstenzivnog prikaza igre. Preciznije, kompletna igra je norma za igru u teoriji igara. Što može jasno izraziti mnoge važne aspekte. Na primer, redosled akcija koje zainteresovane strane mogu da preduzmu, njihov izbor u svakoj tački odlučivanja, informacije o radnjama koje su preduzele druge zainteresovane strane kada svaka zainteresovana strana donosi odluku i koristi od svih mogućih rezultata igre.^[2]

Reference

^ Zuckerman, Inon; Wilson, Brandon; Nau, Dana S. (2018). „Avoiding game-tree pathology in 2-player adversarial search”. Computational Intelligence (на језику: енглески). 34 (2): 542—561. ISSN 1467-8640. S2CID 46926187. doi:10.1111/coin.12162.
^ Huang, Zishuo; Yu, Hang; Chu, Xiangyang; Peng, Zhenwei (2018-05-01). „A novel optimization model based on game tree for multi-energy conversion systems”. Energy (на језику: енглески). 150: 109—121. ISSN 0360-5442. doi:10.1016/j.energy.2018.02.091.

Literatura

Hu, Te Chiang; Shing, Man-tak (2002). Combinatorial Algorithms. Courier Dover Publications. ISBN 0-486-41962-2. Приступљено 2007-04-02.
Judea Pearl, Heuristics, Addison-Wesley, 1984

[1] Zuckerman, Inon; Wilson, Brandon; Nau, Dana S. (2018). „Avoiding game-tree pathology in 2-player adversarial search”. Computational Intelligence (на језику: енглески). 34 (2): 542—561. ISSN 1467-8640. S2CID 46926187. doi:10.1111/coin.12162.

[2] Huang, Zishuo; Yu, Hang; Chu, Xiangyang; Peng, Zhenwei (2018-05-01). „A novel optimization model based on game tree for multi-energy conversion systems”. Energy (на језику: енглески). 150: 109—121. ISSN 0360-5442. doi:10.1016/j.energy.2018.02.091.

[1]

[2]