{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T08:06:35Z","timestamp":1758269195532,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2010,6,1]],"date-time":"2010-06-01T00:00:00Z","timestamp":1275350400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2010,6]]},"abstract":"<jats:p>The incorporation of randomness is critical for the believability and effectiveness of controllers for characters in competitive games. We present a fully automatic method for generating intelligent real-time controllers for characters in such a game. Our approach uses game theory to deal with the ramifications of the characters acting simultaneously, and generates controllers which employ both long-term planning and an intelligent use of randomness. Our results exhibit nuanced strategies based on unpredictability, such as feints and misdirection moves, which take into account and exploit the possible strategies of an adversary. The controllers are generated by examining the interaction between the rules of the game and the motions generated from a parametric motion graph. This involves solving a large-scale planning problem, so we also describe a new technique for scaling this process to higher dimensions.<\/jats:p>","DOI":"10.1145\/1805964.1805970","type":"journal-article","created":{"date-parts":[[2010,6,30]],"date-time":"2010-06-30T20:27:11Z","timestamp":1277929631000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["Character animation in two-player adversarial games"],"prefix":"10.1145","volume":"29","author":[{"given":"Kevin","family":"Wampler","sequence":"first","affiliation":[{"name":"University of Washington, Seattle, WA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik","family":"Andersen","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Evan","family":"Herbst","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yongjoon","family":"Lee","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zoran","family":"Popovi\u0107","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,7,2]]},"reference":[{"volume-title":"Proceedings of the International Conference on Computer Games: Artificial Intelligence, Design and Education.","author":"Graepel T.","key":"e_1_2_2_1_1","unstructured":"Graepel , T. , Herbrich , R. , and Gold , J . 2004. Learning to fight . In Proceedings of the International Conference on Computer Games: Artificial Intelligence, Design and Education. Graepel, T., Herbrich, R., and Gold, J. 2004. Learning to fight. In Proceedings of the International Conference on Computer Games: Artificial Intelligence, Design and Education."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1230100.1230123"},{"key":"e_1_2_2_3_1","doi-asserted-by":"crossref","unstructured":"Ikemoto L. Arikan O. and Forsyth D. 2005. Learning to move autonomously in a hostile environment. Tech. rep. UCB\/CSD-5-1395 University of California at Berkeley.  Ikemoto L. Arikan O. and Forsyth D. 2005. Learning to move autonomously in a hostile environment. Tech. rep. UCB\/CSD-5-1395 University of California at Berkeley.","DOI":"10.1145\/1187112.1187167"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143901"},{"volume-title":"Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence (UAI'02)","author":"Lagoudakis M.","key":"e_1_2_2_5_1","unstructured":"Lagoudakis , M. and Parr , R . 2002. Value function approximation in zero-sum markov games . In Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence (UAI'02) . Lagoudakis, M. and Parr, R. 2002. Value function approximation in zero-sum markov games. In Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence (UAI'02)."},{"volume-title":"Proceedings of the ACM SIGGRAPH\/Eurographics Symposium on Computer Animation. 299--308","author":"Lau M.","key":"e_1_2_2_6_1","unstructured":"Lau , M. and Kuffner , J. J . 2006. Precomputed search trees: Planning for interactive goal-driven animation . In Proceedings of the ACM SIGGRAPH\/Eurographics Symposium on Computer Animation. 299--308 . Lau, M. and Kuffner, J. J. 2006. Precomputed search trees: Planning for interactive goal-driven animation. In Proceedings of the ACM SIGGRAPH\/Eurographics Symposium on Computer Animation. 299--308."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.gmod.2005.03.004"},{"volume-title":"Proceedings of the ACM SIGGRAPH\/Eurographics Symposium on Computer Animation (SCA'06)","author":"Liu C. K.","key":"e_1_2_2_8_1","unstructured":"Liu , C. K. , Hertzmann , A. , and Popovi\u0107 , Z . 2006. Composition of complex optimal multi-character motions . In Proceedings of the ACM SIGGRAPH\/Eurographics Symposium on Computer Animation (SCA'06) . 215--222. Liu, C. K., Hertzmann, A., and Popovi\u0107, Z. 2006. Composition of complex optimal multi-character motions. In Proceedings of the ACM SIGGRAPH\/Eurographics Symposium on Computer Animation (SCA'06). 215--222."},{"volume-title":"Proceedings of the ACM SIGGRAPH\/Eurographics Symposium on Computer Animation (SCA'08)","author":"Lo W.-Y.","key":"e_1_2_2_9_1","unstructured":"Lo , W.-Y. and Zwicker , M . 2008. Real-Time planning for parameterized human motion . In Proceedings of the ACM SIGGRAPH\/Eurographics Symposium on Computer Animation (SCA'08) . Lo, W.-Y. and Zwicker, M. 2008. Real-Time planning for parameterized human motion. In Proceedings of the ACM SIGGRAPH\/Eurographics Symposium on Computer Animation (SCA'08)."},{"key":"e_1_2_2_10_1","volume-title":"Proceedings of the 21st National Conference on Artificial Intelligence. AAAI Press.","author":"Mahadevan S.","year":"2006","unstructured":"Mahadevan , S. 2006 . Learning representation and control in continuous markov decision processes . In Proceedings of the 21st National Conference on Artificial Intelligence. AAAI Press. Mahadevan, S. 2006. Learning representation and control in continuous markov decision processes. In Proceedings of the 21st National Conference on Artificial Intelligence. AAAI Press."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276385"},{"volume-title":"Introduction to Game Theory","author":"Morris P.","key":"e_1_2_2_12_1","unstructured":"Morris , P. 1994. Introduction to Game Theory . Springer . Morris, P. 1994. Introduction to Game Theory. Springer."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/355984.355989"},{"key":"e_1_2_2_14_1","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence. 2574--2579","author":"Petrik M.","year":"2007","unstructured":"Petrik , M. 2007 . An analysis of laplacian methods for value function approximation in mdps . In Proceedings of the International Joint Conference on Artificial Intelligence. 2574--2579 . Petrik, M. 2007. An analysis of laplacian methods for value function approximation in mdps. In Proceedings of the International Joint Conference on Artificial Intelligence. 2574--2579."},{"key":"e_1_2_2_15_1","doi-asserted-by":"crossref","unstructured":"Petrosjan L. and Zenkevich N. 1996. Game Theory. World Scientific.  Petrosjan L. and Zenkevich N. 1996. Game Theory. World Scientific.","DOI":"10.1142\/2875"},{"key":"e_1_2_2_16_1","first-page":"538","article-title":"A monotone iterative algorithm for solving matrix games","volume":"238","author":"Sadovskii A. L.","year":"1978","unstructured":"Sadovskii , A. L. 1978 . A monotone iterative algorithm for solving matrix games . Soviet Math Rep. 238 , 3, 538 -- 540 . Sadovskii, A. L. 1978. A monotone iterative algorithm for solving matrix games. Soviet Math Rep. 238, 3, 538--540.","journal-title":"Soviet Math Rep."},{"volume-title":"Proceedings of the ACM SIGGRAPH\/Eurographics Symposium on Computer Animation (SCA'06)","author":"Shin H. J.","key":"e_1_2_2_17_1","unstructured":"Shin , H. J. and Oh , H. S . 2006. Fat graphs: Constructing an interactive character with continuous controls . In Proceedings of the ACM SIGGRAPH\/Eurographics Symposium on Computer Animation (SCA'06) . Eurographics Association, 291--298. Shin, H. J. and Oh, H. S. 2006. Fat graphs: Constructing an interactive character with continuous controls. In Proceedings of the ACM SIGGRAPH\/Eurographics Symposium on Computer Animation (SCA'06). Eurographics Association, 291--298."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1409060.1409067"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1315184.1315194"},{"key":"e_1_2_2_20_1","volume-title":"Proceedings of the 8th International Symposium on Artificial Intelligence and Mathematics. 25--2004","author":"Smart W. D.","year":"2004","unstructured":"Smart , W. D. 2004 . Explicit manifold representations for value-function approximation in reinforcement learning . In Proceedings of the 8th International Symposium on Artificial Intelligence and Mathematics. 25--2004 . Smart, W. D. 2004. Explicit manifold representations for value-function approximation in reinforcement learning. In Proceedings of the 8th International Symposium on Artificial Intelligence and Mathematics. 25--2004."},{"key":"e_1_2_2_21_1","first-page":"2169","article-title":"Proto-Value functions: A laplacian framework for learning representation and control in markov decision processes","volume":"8","author":"Sridhar M.","year":"2007","unstructured":"Sridhar , M. and Maggioni , M. 2007 . Proto-Value functions: A laplacian framework for learning representation and control in markov decision processes . J. Mach. Learn. Res. 8 , 2169 -- 2231 . Sridhar, M. and Maggioni, M. 2007. Proto-Value functions: A laplacian framework for learning representation and control in markov decision processes. J. Mach. Learn. Res. 8, 2169--2231.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_2_2_22_1","volume-title":"Reinforcement Learning: An Introduction (Adaptive Computation and Machine Learning)","author":"Sutton R. S.","year":"1998","unstructured":"Sutton , R. S. and Barto , A. G . 1998 . Reinforcement Learning: An Introduction (Adaptive Computation and Machine Learning) . The MIT Press . Sutton, R. S. and Barto, A. G. 1998. Reinforcement Learning: An Introduction (Adaptive Computation and Machine Learning). The MIT Press."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276386"},{"volume-title":"Proceedings of the AAAI Fall Symposium on Model Directed Autonomous Systems.","author":"Uther W.","key":"e_1_2_2_24_1","unstructured":"Uther , W. and Veloso , M . 1997. Adversarial reinforcement learning. Tech. rep . In Proceedings of the AAAI Fall Symposium on Model Directed Autonomous Systems. Uther, W. and Veloso, M. 1997. Adversarial reinforcement learning. Tech. rep. In Proceedings of the AAAI Fall Symposium on Model Directed Autonomous Systems."},{"key":"e_1_2_2_25_1","volume-title":"III","author":"Williams R.","year":"1993","unstructured":"Williams , R. and Baird , L. C . III . 1993 . Tight performance bounds on greedy policies based on imperfect value functions. Tech. rep. NU-CCS-93-14. Department of Computer Science, Northeastern University . November. Williams, R. and Baird, L. C. III. 1993. Tight performance bounds on greedy policies based on imperfect value functions. Tech. rep. NU-CCS-93-14. Department of Computer Science, Northeastern University. November."}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1805964.1805970","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1805964.1805970","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:22:42Z","timestamp":1750245762000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1805964.1805970"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,6]]}},"alternative-id":["10.1145\/1805964.1805970"],"URL":"https:\/\/doi.org\/10.1145\/1805964.1805970","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"type":"print","value":"0730-0301"},{"type":"electronic","value":"1557-7368"}],"subject":[],"published":{"date-parts":[[2010,6]]},"assertion":[{"value":"2010-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-07-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}