EXPERIMENTS WITH ONLINE REINFORCEMENT LEARNING IN REAL-TIME STRATEGY GAMES

Real-time strategy (RTS) games provide a challenging platform to implement online reinforcement learning (RL) techniques in a real application. Computer, as one game player, monitors opponents’ (human or other computers) strategies and then updates its own policy using RL methods. In this article, we first examine the suitability of applying the online RL in various computer games. Reinforcement learning application depends on both RL complexity and the game features. We then propose a multi-layer framework for implementing online RL in an RTS game. The framework significantly reduces RL computational complexity by decomposing the state space in a hierarchical manner. We implement an RTS game—Tank General—and perform a thorough test on the proposed framework. We consider three typical profiles of RTS game players and compare two basic RL techniques applied in the game. The results show the effectiveness of our proposed framework and shed light on relevant issues in using online RL in RTS games.     

计算机扑克智能博弈研究综述

计算机博弈是人工智能领域的“果蝇”,备受人工智能领域研究者的关注,已然成为研究认知智能的有利平台。扑克类博弈对抗问题可建模成边界确定、规则固定的不完美信息动态博弈,计算机扑克 AI 需要具备不完全信息动态决策、对手误导欺诈行为识别以及多回合筹码和风险管理等能力。首先梳理了以德州扑克为代表的计算机扑克智能博弈的发展历程,其次针对计算机扑克智能博弈典型模型算法、关键技术以及存在的主要问题进行了综述分析,最后探讨了计算机扑克智能博弈的未来发展趋势和应用前景。     

Interactive story authoring: A viable form of creative expression for the classroom

The unprecedented growth in numbers of children playing computer games has stimulated discussion and research regarding what, if any, educational value these games have for teaching and learning. The research on this topic has primarily focused on children as players of computer games rather than builders/constructors of computer games. Recently, several game companies, such as BioWare Corp. and Bethesda Softworks, have released game story creation tools to the public, along with their games. However, a major obstacle to using these commercial tools is the level of programming experience required to create interactive game stories. In this paper, we demonstrate that a commercial game story construction tool, BioWare Corp.’s Aurora Toolset, can be augmented by our new tool, ScriptEase, to enable students in two grade ten English classes to successfully construct interactive game stories. We present evidence that describes the relationship between interactive story authoring and traditional story authoring, along with a series of factors that can potentially affect success at these activities: gender, creativity, intellectual ability, previous experiences with programming, time playing computer games, and time spent online. Results indicate that students can successfully construct sophisticated interactive stories with very little training. The results also show no gender differences in the quality of these interactive stories, regardless of programming experience or the amount of time per week playing computer games or participating in general online activities, although a subset of female students did show a slightly higher level of performance on interactive story authoring. In the educational context of this study, we show that ScriptEase provides an easy-to-use tool for interactive story authoring in a constructionist learning environment.     

TOWARDS OPTIMIZING ENTERTAINMENT IN COMPUTER GAMES

Mainly motivated by the current lack of a qualitative and quantitative entertainment formulation of computer games and the procedures to generate it, this article covers the following issues: It presents the features—extracted primarily from the opponent behavior—that make a predator/prey game appealing; provides the qualitative and quantitative means for measuring player entertainment in real time, and introduces a successful methodology for obtaining games of high satisfaction. This methodology is based on online (during play) learning opponents who demonstrate cooperative action. By testing the game against humans, we confirm our hypothesis that the proposed entertainment measure is consistent with the judgment of human players. As far as learning in real time against human players is concerned, results suggest that longer games are required for humans to notice some sort of change in their entertainment.     

The effectiveness of adaptive difficulty adjustments on students' motivation and learning in an educational computer game

Computer games that adaptively adjust difficulty are used to continuously challenge players according to their abilities. The adjustment of difficulty occurs automatically in response to a game's ongoing assessment of a player's performance. This approach to difficulty adjustment is likely to be of value in educational computer games as a means of scaffolding learning for students. However, there is limited research evaluating the effectiveness of educational computer games with adaptive difficulty adjustment when compared to non-adaptive difficulty adjustment. To expand on this research a quasi-experimental study was designed to isolate the impact of the difficulty adjustment game element on motivation and learning. A total of 234 secondary school students were allocated to one of three activities involving learning about Spanish cognates: an adaptive difficulty adjustment game, an incremental difficulty adjustment game that was non-adaptive, and a written activity. The three learning activities were designed following the same learning and motivation theories. The two games were identical apart from the difficulty adjustment mechanism. The results for motivation indicated that all students experienced high levels and there was no significant difference between the three learning activities. The pre- and post-tests results for learning indicated that significantly higher learning outcomes were achieved by students who played the adaptive game. Analysis of a game log recording the correctness of students' responses indicated that the adaptive difficulty adjustment game, in contrast to the non-adaptive incremental difficulty adjustment game, provided a scaffolding structure to enhance student learning.     

Multiplayer online games as educational tools: Facing new challenges in learning

This paper outlines a proposal for the development of educational multiplayer online games based on the activity theory, as an alternative to the current trend in multiplayer gaming and a means of promoting collaboration among students. In order to examine whether online games are engaging for learners, we consider multiple factors regarding game play – such as frequency of game use, gender differences, identification with the characters, and game preferences – as well as some psychosocial factors that may influence learning – such as academic performance, self-esteem, and computer self-efficacy. This paper suggests that online multiplayer educational games should be approached as a complex learning system, based on the principles of activity theory, where the Subjects would interact with other Subjects, Objects and Tools of the game, under specified Rules and create Communities through division of labor, leading to the expected learning outcome. Thus, we suggest taking into account some important issues concerning the Subjects that the activity theory refers to, such as gender differences in playing games, academic performance, self-esteem and computer self-efficacy.     

Knowledge Condition Games

Understanding the flow of knowledge in multi-agent protocols is essential when proving the correctness or security of such protocols. Current logical approaches, often based on model checking, are well suited for modeling knowledge in systems where agents do not act strategically. Things become more complicated in strategic settings. In this paper we show that such situations can be understood as a special type of game – a knowledge condition game – in which a coalition “wins” if it is able to bring about some epistemic condition. This paper summarizes some results relating to these games. Two proofs are presented for the computational complexity of deciding whether a coalition can win a knowledge condition game with and without opponents (Σ₂P-complete and NP-complete respectively). We also consider a variant of knowledge condition games in which agents do not know which strategies are played, and prove that under this assumption, the presence of opponents does not affect the complexity. The decision problem without opponents is still NP-complete, but requires a different proof.Sieuwert van Otterloo thanks the Institute for Logic, Language and Information in Amsterdam for its hospitality during the period that this paper was finalized.     

A general criterion and an algorithmic framework for learning in multi-agent systems

We offer a new formal criterion for agent-centric learning in multi-agent systems, that is, learning that maximizes one’s rewards in the presence of other agents who might also be learning (using the same or other learning algorithms). This new criterion takes in as a parameter the class of opponents. We then provide a modular approach for achieving effective agent-centric learning; the approach consists of a number of basic algorithmic building blocks, which can be instantiated and composed differently depending on the environment setting (for example, 2- versus n-player games) as well as the target class of opponents. We then provide several specific instances of the approach: an algorithm for stationary opponents, and two algorithms for adaptive opponents with bounded memory, one algorithm for the n-player case and another optimized for the 2-player case. We prove our algorithms correct with respect to the formal criterion, and furthermore show the algorithms to be experimentally effective via comprehensive computer testing.     

Dynamic Bayesian approach for detecting cheats in multi-player online games

Massively multi-player games hold a huge market in the digital entertainment industry. Companies invest heavily in game developments since a successful online game can attract millions of users, and this translates to a huge investment payoff. However, multi-player online games are also subjected to various forms of “hacks” and “cheats”. Hackers can alter the graphic rendering to reveal information otherwise be hidden in a normal game, or cheaters can use software robots to play the game automatically and thus gain an unfair advantage. To overcome these problems, some popular online games release software patches constantly to block “known” hacks or incorporate anti-cheating software to detect “known” cheats. This not only creates deployment difficulty but new cheats will still be able to breach the normal game logic until software patches or updates of the anti-cheating software are available. Moreover, the anti-cheating software themselves are also vulnerable to hacks. In this paper, we propose a “scalable” and “efficient” method to detect whether a player is cheating or not. The methodology is based on the dynamic Bayesian network approach. The detection framework relies solely on the game states and runs in the game server only. Therefore, it is invulnerable to hacks and it is a much more deployable solution. To demonstrate the effectiveness of the proposed method, we have implemented a prototype multi-player game system to detect whether a player is using any “aiming robot” for cheating or not. Experiments show that the proposed method can effectively detect cheaters on a first-person shooter game with extremely low false positive rate. We believe the proposed methodology and the prototype system provide a first step toward a systematic study of cheating detection and security research in the area of online multi-player games.     

Who but not where: The effect of social play on immersion in digital games

The majority of digital games available today offer a variety of multi-player settings including co-located and mediated play between opponents. Immersion, the sense of being “in the game,” is one of the key components of the gaming experience but existing literature suggests that social play provides more fun but less immersion. There is however little empirical support for this. This paper therefore addresses the question: how does playing digital games in a social situation alter the sense of immersion felt by the individuals playing? This paper presents three experiments that test the relationship between social setting and immersion. The three experiments aim to manipulate the social setting in which players play, be it against a computer, against a person online or against a co-located person. Overall the three experiments show that players are more immersed when playing against another person rather than playing against a computer but there is no significant difference in immersion whether the other person is online or in the same room. This refutes previous claims about social play reducing immersion and indeed that social play enhances the sense of being in the game where interaction is through the game.     

Effects of Interactivity in Educational Games: A Mediating Role of Social Presence on Learning Outcomes

Networked interactivity is one of the essential factors that differentiate recent online educational games from traditional stand-alone CD-based games. Despite the growing popularity of online educational games, empirical studies about the effects of networked interactivity are relatively rare. The current study tests the effects of networked interactivity on game users' learning outcomes by comparing three groups (online educational quiz game vs. off-line educational quiz game vs. traditional classroom lecture). In addition, the study examines the mediating role of social presence in the context of educational games. Results indicate that networked interactivity in the online educational quiz game condition enhances game users' positive evaluation of learning, test performance, and feelings of social presence. However, there was no significant difference between the off-line educational quiz game and the lecture-based conditions in terms of learning outcomes. Further analyses indicate that feelings of social presence mediate the effect of networked interactivity on various learning outcomes. Theoretical and practical implications are discussed.     

Improving behavior of computer game bots using fictitious play

In modern computer games, "bots" - intelligent realistic agents play a prominent role in the popularity of a game in the market. Typically, bots are modeled using finite-state machine and then programmed via simple conditional statements which are hard-coded in bots logic. Since these bots have become quite predictable to an experienced games player, a player might lose interest in the game. We propose the use of a game theoretic based learning rule called fictitious play for improving behavior of these computer game bots which will make them less predictable and hence, more a enjoyable game.     

Effectiveness of MMORPG‐based instruction in elementary English education in Korea

This study investigated the effectiveness of massive multiplayer online role‐playing game (MMORPG)‐based (massive multiplayer online role‐playing game) instruction in elementary English education. The effectiveness of the MMORPG program was compared with face‐to‐face instruction and the independent variables (gender, prior knowledge, motivation for learning, self‐directed learning skills, computer skills, game skills, computer capacity, network speed, and computer accessibility) were examined to see how accurately achievement was predicted in MMORPG instruction. The results indicated that students studying English utilizing online role‐playing games showed higher scores in areas of listening, reading, and writing than those who attended face‐to‐face instruction classes. It was also found that prior knowledge, motivation for learning, and network speed were factors affecting achievement in English learning. These findings suggest that MMORPGs can play an important role in improving English communicative skills.     

The differences in motivations of online game players and offline game players: A combined analysis of three studies at higher education level

Computer games have become a highly popular form of entertainment and have had a large impact on how University students spend their leisure time. Due to their highly motivating properties computer games have come to the attention of educationalists who wish to exploit these highly desirable properties for educational purposes. Several studies have been performed looking at motivations for playing computer games in a general context and in a Higher Education (HE) context. These studies did not focus on the differences in motivations between online and offline game players. Equally the studies did not look at the differences in motivations of people who prefer single player games and people who prefer multiplayer games. If games-based learning is to become a recognised teaching approach then such motivations for playing computer games must be better understood. This paper presents the combined analysis of three studies at HE level, performed over a four year period from 2005 to 2009. The paper focuses on differences of motivations in relation to single player/multiplayer preference and online/offline game participation. The study found that challenge is the top ranking motivation and recognition is the lowest ranking motivation for playing computer games in general. Challenge is also the top ranking motivation for playing games in HE while fantasy and recognition are the lowest ranking motivations for playing games in HE. Multiplayer gamers derive more competition, cooperation, recognition, fantasy and curiosity from playing games and online gamers derive more challenge, cooperation, recognition and control from playing games. Multiplayer gamers and online gamers ranked competition, cooperation and recognition significantly more important for playing games in HE than single players and offline participants.     

一种针对德州扑克AI的对手建模与策略集成框架

以德州扑克游戏为代表的大规模不完美信息博弈是现实世界中常见的一种博弈类型.现有以求解纳什均衡策略为目标的主流德州扑克求解算法存在依赖博弈树模型、算力消耗大、策略过于保守等问题,导致智能体在面对不同对手时无法最大化自身收益.为解决上述问题,提出一种轻量高效且能快速适应对手策略变化进而剥削对手的不完美信息博弈求解框架.本框...     

Strategic best-response learning in multiagent systems

We present a novel and uniform formulation of the problem of reinforcement learning against bounded memory adaptive adversaries in repeated games, and the methodologies to accomplish learning in this novel framework. First we delineate a novel strategic definition of best response that optimises rewards over multiple steps, as opposed to the notion of tactical best response in game theory. We show that the problem of learning a strategic best response reduces to that of learning an optimal policy in a Markov Decision Process (MDP). We deal with both finite and infinite horizon versions of this problem. We adapt an existing Monte Carlo based algorithm for learning optimal policies in such MDPs over finite horizon, in polynomial time. We show that this new efficient algorithm can obtain higher average rewards than a previously known efficient algorithm against some opponents in the contract game. Though this improvement comes at the cost of increased domain knowledge, simple experiments in the Prisoner's Dilemma, and coordination games show that even when no extra domain knowledge (besides that an upper bound on the opponent's memory size is known) is assumed, the error can still be small. We also experiment with a general infinite-horizon learner (using function-approximation to tackle the complexity of history space) against a greedy bounded memory opponent and show that while it can create and exploit opportunities of mutual cooperation in the Prisoner's Dilemma game, it is cautious enough to ensure minimax payoffs in the Rock–Scissors–Paper game.     

Playing online games against computer- vs. human-controlled opponents: Effects on presence,flow, and enjoyment

The purpose of this study was to examine whether playing online games against other users leads to different experiences in comparison with playing against computer-controlled opponents. Thereby, a one-factorial multivariate design was used (computer-controlled vs. human-controlled opponent). Dependent variables were the participants’ feelings of presence and flow. Additionally, the amount of enjoyment was measured. The findings indicate that the type of opponent influences playing experiences: participants who played against a human-controlled opponent reported more experiences of presence, flow, and enjoyment, whereby the strongest effect refers to the experience of presence. Furthermore, strong relations between presence, flow, and enjoyment were observed. Further analyzes suggest that flow mediates the relationship between presence and enjoyment.     

Towards the design and implementation of computer-modeled opponents for use in entertainment and educational software: Some initial considerations

While advances in computer technology have led to major improvements in the presentation and appearance of modern computer games, there has been no equivalent improvement in the artificial intelligence (AI) performance of these games. Traditional AI designs have had surprisingly little impact on the development of game-based intelligent systems. New approaches to AI, particularly those using autonomous software agents encapsulated in software robots (softbots), have the potential to make an enormous impact on game-based AI systems.Softbot-based autonomous software agents provide a framework capable of supporting psychologically based models of human behavior in a game environment. Used in this manner, softbots provide a new set of tools to explore the synthesis of human-like reasoning in complex and dynamic environments.This paper explores some initial attempts to develop an exploratory, game-based, experimental environment capable of hosting softbot-based, psychological models of human behavior. Some preliminary work in the design and implementation of a simple, extensible, softbot-based, computer-modeled opponent is also discussed.     

面向人工智能专业课程的棋类博弈教学辅助平台

针对人工智能类课程博弈算法理论性太强、算法较复杂和抽象等问题,设计并实现功能较为完整、用户界面友好的棋类博弈教学辅助平台,平台允许用户上传编写好的博弈程序,实现博弈程序间对弈、人与博弈程序对弈以及人人对弈。本文阐述了棋类博弈教学辅助平台的总体设计、主要功能模块以及搭建平台采用的核心技术。棋类博弈教学平台的设计有益于培养学生依据所学理论知识来解决实际问题的能力,促进学生对计算机博弈程序和人工智能方法的不断探索改进,以达到更好的教学效果。本文进一步评估了棋类博弈平台在人工智能课程的实际使用情况与实践效果。