Is Minimax really an optimal strategy in games

• Autorzy: Kościuk K.

Warianty tytułu

PL

Czy Minimax jest rzeczywście optymalną strategią w grach?

• Języki publikacji: EN

Abstrakty

EN

In theory, the optimal strategy for all kinds of games against an intelligent opponent is the Minimax strategy. Minimax assumes a perfectly rational opponent, who also takes optimal actions. However, in practice, most human opponents depart from rationality. In this case, the best move at any given step may not be one that is indicated by Minimax and an algorithm that takes into consideration human imperfections will perform better. In this paper, we show how modeling an opponent and subsequent modification of the Minimax strategy that takes into account that the opponent is not perfect, can improve a variant of the Tic-Tac-Toe game and and the game of Bridge. In Bridge we propose a simple model, in which we divide players into two classes: conservative and risk-seeking. We show that knowing which class the opponent belongs to improves the performance of the algorithm.

PL

Algorytmy grające w gry często używają strategii Minimax. Algorytm Minimax zakłada perfekcyjność przeciwnika, który wybiera zawsze najlepsze ruchy. Gracze jednakże mogą nie działać całkiem racjonalnie. Algorytm, który weźmie to pod uwagę może dawać lepsze wyniki niż Minimax. W pracy przedstawiono jak modelowanie gracza i modyfikacje algorytmu Minimax mogą poprawić wyniki w grze kółko-krzyżyk i w brydżu. W brydżu zaproponowany został prosty model, dzielący graczy na dwie kategorie - konserwatywny i ryzykowny. Eksperymenty pokazały, że wiedza, do której klasy graczy należy przeciwnik, poprawia działanie algorytmu.

Słowa kluczowe

EN

Minimax; optimality; player modeling; bridge

PL

Minimax; optymalność; modelowanie gracza; brydż

• Wydawca: Oficyna Wydawnicza Politechniki Białostockiej
• Czasopismo: Zeszyty Naukowe Politechniki Białostockiej. Informatyka
• Rocznik: 2010
• Tom: Z. 6
• Strony: 63--75
• Opis fizyczny: Bibliogr. 9 poz., rys.

Twórcy

autor

Kościuk K.

• Politechnika Białostocka, Wydział Informatyki, Białystok

Bibliografia

• [1] Ginsberg, M., L.: GIB: Imperfect Information in a Computationally Challenging Game. Journal of Artificial Intelligence Research 14, 2001, pp. 303–38.
• [2] Levy, D.: The million pound bridge program, Heuristic Programming in Artificial Intelligence: The First Computer Olympiad. Chichester, UK: Ellis Horwood, 1989.
• [3] Kościuk, K., Dru˙zd˙zel, M.: Exploring opponent’s weaknesses as an alternative to the Minimax strategy. XV Warsztaty Naukowe PTSK : Symulacja w badaniach i rozwoju, 2008.
• [4] Kościuk, K., Dru˙zd˙zel, M.: Player Modeling Using Bayesian Network. XVI Warsztaty Naukowe PTSK : Symulacja w badaniach i rozwoju, 2009.
• [5] von Neumann, J., Morgenstern, O.: Theory of Games and Economic Behavior. Princeton University Press, 1944.
• [6] Pearl, J.: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. San Mateo, CA: Morgan Kaufmann Publishers, 1988.
• [7] Simon, H., A.: A Behavioral Model of Rational Choice. The Quarterly Journal of Economics 69, No. 1, 1955, pp. 99–118.
• [8] [http://www.kurnik.pl]
• [9] [http://web2.acbl.org/laws/rlaws/lawofcontractbridgecombined_ 2004.pdf]