Christopher Archibald

AAAI Conference 2025 Conference Paper

Improving Cooperation in Language Games with Bayesian Inference and the Cognitive Hierarchy

• Joseph Bills
• Christopher Archibald
• Diego Blaylock

In two-player cooperative games, agents can play together effectively when they have accurate assumptions about how their teammate will behave, but may perform poorly when these assumptions are inaccurate. In language games, failure may be due to disagreement in the understanding of either the semantics or pragmatics of an utterance. We model coarse uncertainty in semantics using a prior distribution of language models and uncertainty in pragmatics using the cognitive hierarchy, combining the two aspects into a single prior distribution over possible partner types. Fine-grained uncertainty in semantics is modeled using noise that is added to the embeddings of words in the language. To handle all forms of uncertainty we construct agents that learn the behavior of their partner using Bayesian inference and use this information to maximize the expected value of a heuristic function. We test this approach by constructing Bayesian agents for the game of Codenames, and show that they perform better in experiments where semantics is uncertain.

ECAI Conference 2024 Conference Paper

Approximate Estimation of High-Dimension Execution Skill for Dynamic Agents in Continuous Domains

• Delma Nieves-Rivera
• Christopher Archibald

In many real-world continuous action domains, human agents must decide which actions to attempt and then execute those actions to the best of their ability. However, humans cannot execute actions without error. Human performance in these domains can potentially be improved by the use of AI to aid in decision-making. One requirement for an AI to correctly reason about what actions a human agent should attempt is a correct model of that human’s execution error, or skill. Recent work has demonstrated successful techniques for estimating this execution error with various types of agents across different domains. However, this previous work made several assumptions that limit the application of these ideas to real-world settings. First, previous work assumed that the error distributions were symmetric normal, which meant that only a single parameter had to be estimated. In reality, agent error distributions might exhibit arbitrary shapes and should be modeled more flexibly. Second, it was assumed that the execution error of the agent remained constant across all observations. Especially for human agents, execution error changes over time, and this must be taken into account to obtain effective estimates. To overcome both of these shortcomings, we propose a novel particle-filter-based estimator for this problem. After describing the details of this approximate estimator, we experimentally explore various design decisions and compare performance with previous skill estimators in a variety of settings to showcase the improvements. The outcome is an estimator capable of generating more realistic, time-varying execution skill estimates of agents, which can then be used to assist agents in making better decisions and improve their overall performance.

JAIR Journal 2024 Journal Article

Estimating Agent Skill in Continuous Action Domains

• Christopher Archibald
• Delma Nieves-Rivera

Actions in most real-world continuous domains cannot be executed exactly. An agent’s performance in these domains is influenced by two critical factors: the ability to select effective actions (decision-making skill), and how precisely it can execute those selected actions (execution skill). This article addresses the problem of estimating the execution and decision-making skill of an agent, given observations. Several execution skill estimation methods are presented, each of which utilize different information from the observations and make assumptions about the agent’s decision-making ability. A final novel method forgoes these assumptions about decision-making and instead estimates the execution and decision-making skills simultaneously under a single Bayesian framework. Experimental results in several domains evaluate the estimation accuracy of the estimators, especially focusing on how robust they are as agents and their decision-making methods are varied. These results demonstrate that reasoning about both types of skill together significantly improves the robustness and accuracy of execution skill estimation. A case study is presented using the proposed methods to estimate the skill of Major League Baseball pitchers, demonstrating how these methods can be applied to real-world data sources.

AAAI Conference 2019 Conference Paper

Bayesian Execution Skill Estimation

• Christopher Archibald
• Delma Nieves-Rivera

The performance of agents in many domains with continuous action spaces depends not only on their ability to select good actions to execute, but also on their ability to execute planned actions precisely. This ability, which has been called an agent’s execution skill, is an important characteristic of an agent which can have a significant impact on their success. In this paper, we address the problem of estimating the execution skill of an agent given observations of that agent acting in a domain. Each observation includes the executed action and a description of the state in which the action was executed and the reward received, but notably excludes the action that the agent intended to execute. We previously introduced this problem and demonstrated that estimating an agent’s execution skill is possible under certain conditions. Our previous method focused entirely on the reward that the agent received from executed actions and assumed that the agent was able to select the optimal action for each state. This paper addresses the execution skill estimation problem from an entirely different perspective, focusing instead on the action that was executed. We present a Bayesian framework for reasoning about action observations and show that it is able to outperform previous methods under the same conditions. We also show that the flexibility of this framework allows it to be applied in settings where the previous limiting assumptions are not met. The success of the proposed method is demonstrated experimentally in a toy domain as well as the domain of computational billiards.

AAMAS Conference 2018 Conference Paper

Execution Skill Estimation

• Christopher Archibald
• Delma Nieves-Rivera

In domains with continuous action spaces, one characteristic of an agent is their precision in executing intended actions. An agent’s execution skill significantly impacts their success as it determines how much executed actions deviate from intended actions. We introduce the problem of estimating an agent’s execution skill level given only observations of their executed actions. The main difficulty is that while executed actions are observed, the intended actions are not, thus the amount of action deviation due to imperfect execution skill is not obvious. We introduce a simple experimental domain in which this problem can be studied and present a method that focuses on observed rewards to estimate execution skill. This method is experimentally evaluated and shown be able to estimate an agent’s execution skill under certain conditions.

AAAI Conference 2013 Conference Paper

Automating Collusion Detection in Sequential Games

• Parisa Mazrooei
• Christopher Archibald
• Michael Bowling

Collusion is the practice of two or more parties deliberately cooperating to the detriment of others. While such behavior may be desirable in certain circumstances, in many it is considered dishonest and unfair. If agents otherwise hold strictly to the established rules, though, collusion can be challenging to police. In this paper, we introduce an automatic method for collusion detection in sequential games. We achieve this through a novel object, called a collusion table, that captures the effects of collusive behavior, i. e. , advantage to the colluding parties, without assuming any particular pattern of behavior. We show the effectiveness of this method in the domain of poker, a popular game where collusion is prohibited.

AAMAS Conference 2013 Conference Paper

Rating Players in Games with Real-Valued Outcomes

• Christopher Archibald
• Neil Burch
• Michael Bowling
• Matthew Rutherford

Game-theoretic models typically associate outcomes with real valued utilities, and rational agents are expected to maximize their expected utility. Currently fielded agent rating systems, which aim to order a population of agents by strength, focus exclusively on games with discrete outcomes, e. g. , win-loss in two-agent settings or an ordering in the multi-agent setting. These rating systems are not well-suited for domains where the absolute magnitude of utility rather than just the relative value is important. We introduce the problem of rating agents in games with real-valued outcomes and survey applicable existing techniques for rating agents in this setting. We then propose a novel rating system and an extension for all of these rating systems to games with more than two agents, showing experimentally the advantages of our proposed system.

IJCAI Conference 2011 Conference Paper

Hustling in Repeated Zero-Sum Games with Imperfect Execution

• Christopher Archibald
• Yoav Shoham

We study repeated games in which players have imperfect execution skill and one player's true skill is not common knowledge. In these settings the possibility arises of a player "hustling, " or pretending to have lower execution skill than they actually have. Focusing on repeated zero-sum games, we provide a hustle-proof strategy; this strategy maximizes a player's payoff, regardless of the true skill level of the other player.

AAMAS Conference 2010 Conference Paper

Success, strategy and skill: an experimental study

• Christopher Archibald
• Alon Altman
• Yoav Shoham

In many AI settings an agent is comprised of both action-planning and action-execution components. We examine the relationship between the precision of the execution component, the intelligence of the planning component, and the overall success of the agent. Our motivation lies in determining whether higher execution skill rewards more strategic playing. We present a computational billiards framework in which the interaction between skill and strategy can be experimentally investigated. By comparing the performance of different agents with varying levels of skill and strategic intelligence we show that intelligent planning can contribute most to an agent's success when that agent has imperfect skill.

IJCAI Conference 2009 Conference Paper

• Christopher Archibald
• Alon Altman
• Yoav Shoham

We discuss CUECARD, the program that won the 2008 Computer Olympiad computational pool tournament. Beside addressing intrinsic interest in a complex competitive environment with unique features, our goal is to isolate the factors that contributed to the performance so that the lessons can be transferred to other, similar domains. Specifically, we distinguish among pure engineering factors (such as using a computer cluster), domainspecific factors (such as optimized break shots), and domain-independentfactors (such as state clustering). Our conclusion is that each type of factor contributed to the performance of the program.

AAMAS Conference 2009 Conference Paper

Modeling Billiards Games

• Christopher Archibald
• Yoav Shoham

Two-player games of billiards, of the sort seen in recent Computer Olympiads held by the International Computer Games Association, are an emerging area with unique challenges for A. I. research. Complementing the heuristic/algorithmic aspect of billiards, of the sort brought to the fore in the ICGA billiards tournaments, we investigate formal models of such games. The modeling is surprisingly subtle. While sharing features with existing models (including stochastic games, games on a square, recursive games, and extensive form games), our model is distinct, and consequently requires novel analysis. We focus on the basic question of whether the game has an equilibrium. For finite versions of the game it is not hard to show the existence of a pure strategy Markov perfect Nash equilibrium. In the infinite case, it can be shown that under certain conditions a stationary pure strategy Markov perfect Nash equilibrium is guaranteed to exist.