Questions tagged [game-theory]

For questions regarding the use of the mathematical theory of games (Von Neumann, Morgenstern, Nash etc) in AI. For questions about the use of AI in game design and gaming, use [gaming].

Filter by
Sorted by
Tagged with
11 votes
3 answers
2k views

Why spend so much time and money to build AIs to play games?

I was reading about John McCarthy and his orthodox vision of Artificial Intelligence. To me, it seems like he was not very much in favour of resources (like time and money) being used to make AIs play ...
Suraj Shah's user avatar
8 votes
3 answers
4k views

Is there any board game where a human can still beat an AI?

Significant AI vs human board game matches include: chess: Deep Blue vs Kasparov in 1996, go: DeepMind AlphaGo vs Lee Sedol in 2016, which demonstrated that AI challenged and defeated professional ...
kenorb's user avatar
  • 10.5k
6 votes
3 answers
1k views

Perfect play in information incomplete games

As titled, is there such thing as perfect play (or at least "perfectly optimal") in a game with incomplete information? Or at least a proof as to show why there cannot? Naively (and seemingly ...
k.c. sayz 'k.c sayz''s user avatar
6 votes
2 answers
725 views

Are perfect and imperfect information games modelled as fully and partially observable environments, respectively?

In perfect information games, the agent can see all the moves performed in the past. Besides, it can observe the next action that will be put into practice by the opponent. In this case, can we say ...
Goktug's user avatar
  • 161
6 votes
1 answer
176 views

Interesting examples of discrete stochastic games

SGs are a generalization of MDPs to multiple agents. Like this previous question on MDPs, are there any interesting examples of zero-sum, discrete SGs—preferably with small state and action spaces? I'...
user76284's user avatar
  • 347
5 votes
1 answer
873 views

What's the optimal policy in the rock-paper-scissors game?

A deterministic policy in the rock-paper-scissors game can be easily exploited by the opponent - by doing just the right sequence of moves to defeat the agent. More often than not, I've heard that a ...
stoic-santiago's user avatar
5 votes
1 answer
315 views

Why do zero-sum perfect information games satisfy the conditions of Von Neumann's theorem?

The Von Neumann's Minimax theorem gives the conditions that make the max-min inequality an equality. I understand the max-min inequality, basically ...
dontloo's user avatar
  • 167
4 votes
1 answer
2k views

Why is tic-tac-toe considered a non-deterministic environment?

I have been reading about deterministic and stochastic environments, when I came up with an article that states that tic-tac-toe is a non-deterministic environment. But why is that? An action will ...
EEAH's user avatar
  • 193
4 votes
2 answers
382 views

What is the difference between genetic algorithms and evolutionary game theory algorithms?

What is the difference between genetic algorithms and evolutionary game theory algorithms?
DRV's user avatar
  • 1,673
4 votes
1 answer
472 views

How can an AI play Flow Free?

The game "Flow Free" in which you connect coloured dots with lines is very popular. A human can learn techniques to play it. I was wondering how an AI might approach it. There are certain rules of ...
zooby's user avatar
  • 2,196
4 votes
2 answers
509 views

How to define or represent evil in logic

Is there any well defined method to define or represent evil in abstract logic, binary or AI form? Video games method of representing evil is relative to the player context (thus subjective, and not ...
Jawad Al Shaikh's user avatar
4 votes
1 answer
397 views

What is the state-space complexity of Spades?

AI reached super-human level in many complex games, including imperfect information games such as six-player no-limit Texas hold’em poker. However, it still did not reached that level in Trick-taking ...
Cohensius's user avatar
  • 413
4 votes
1 answer
318 views

Can minimax be used when both players want to increase their score?

If both the players want to increase their score (by selecting the highest or best cost path), can this be done using the minimax algorithm, or are there other algorithms for this purpose?
Rachael E's user avatar
3 votes
3 answers
5k views

How to calculate the optimal placements for settlements in Catan without an ML algorithm?

Is it possible to calculate the best possible placements for settlements in Catan without using an ML algorithm? While it is trivial to simply add up the numbers surrounding the settlement (highest ...
acj11507's user avatar
3 votes
4 answers
5k views

If two perfect chess AI's played each other, would it always be a stalemate or would white win for an inherent first-move advantage?

In the circumstances of two perfect AI's playing each other, will white have an inherent advantage? Or can black always play for a stalemate by countering every white strategy?
maviz's user avatar
  • 131
3 votes
2 answers
4k views

How to make minimax optimal?

By optimal I mean that: If max has a winning strategy then minimax will return the strategy for max with the fewest number of moves to win. If min has a winning strategy then minimax will return the ...
Aadit M Shah's user avatar
3 votes
1 answer
394 views

Why does our AI play worse at even levels of depth?

We are building an AI to play a board game. Leaving aside the implementation, we noticed that it plays worse when we set an even (2,4,6,...) level of depth. We use a minimax depth-first strategy. Do ...
Tom Dwan's user avatar
3 votes
1 answer
213 views

Is there a way to predict points on a map?

I have a data set with historical information of some events (let's say event A and event B),these events describe the discovery of land mines, the coordinates of the event and the date of the event; ...
gerard's user avatar
  • 73
3 votes
0 answers
142 views

What are some strong algorithms for Perfect Information, Deterministic Multiplayer Games?

I have a series of games with the following properties: 3 or more players, but purely non-cooperative (i.e., no coalition forming); sequential moves; perfect information; deterministic state ...
MikeRand's user avatar
  • 131
3 votes
0 answers
368 views

What is the state of the art AI training technique for imperfect information 2 player turn based games?

As far as I can tell (correct me if I'm wrong), Alphazero (with MCTS and neural network heuristic function RL) is the state of the art training method for turn based, deterministic, perfect ...
Bridgeburners's user avatar
3 votes
0 answers
76 views

Negative counterfactual regret

I am reading the paper Regret Minimization in Games with Incomplete Information on CFR algorithm. On page 4, the paper defines $R^{T,+}_{i,\text{imm}}=\max\{R^{T}_{i,\text{imm}}, 0\}$ after equation (...
user69818's user avatar
  • 131
3 votes
0 answers
78 views

Is there a measure of AI relative strength, modified by resources?

For instance, Strength/Size$\times$Speed, where size and speed refer to memory and processing. We now have very strong, narrow AI, but they tend to run on fast hardware without volume restrictions. To ...
DukeZhou's user avatar
  • 6,237
2 votes
2 answers
300 views

What is the difference between game theory and machine learning?

What is the difference between game theory and machine learning? I had gone through the papers Deep Learning for Predicting Human Strategic Behavior, by Jason Hartford et al., and When Machine ...
DRV's user avatar
  • 1,673
2 votes
2 answers
170 views

AI with conflicting objectives?

A recent question on AI and acting recalled me to the idea that in drama, there are not only conflicting motives between agents (characters), but a character may themselves have objectives that are in ...
DukeZhou's user avatar
  • 6,237
2 votes
1 answer
215 views

Is there any flaw to this solution to the One shot prisoner's dilemma

I wrote a solution to the one shot Prisoner's dilemma:     Introduction My solution applies to a prisoner dilemma involving two people (I have neither sufficient knowledge of the prisoner'...
Tobi Alafin's user avatar
2 votes
0 answers
89 views

When to model decision-making problem as single agent vs multi-agent problem?

I understand the goals and purposes of RL in the case of a single agent and the underlying model, i.e. MDPs, for RL problems (or sequential decision making with uncertainty in general). My question is ...
David's user avatar
  • 121
2 votes
1 answer
202 views

How are the Bellman optimality equations and minimax related?

Is the philosophy between Bellman equations and minimax the same? Both the algorithms look at the full horizon and take into account potential gains (Bellman) and potential losses (minimax). ...
gfdsal's user avatar
  • 171
2 votes
0 answers
37 views

Impact or applications of introducing attention in deep networks modelling multi-agent systems

I have been reading quite a lot about the research progress in the domain of self attention-based neural networks that were introduced by Google Inc. in their paper titled "Attention is all you ...
Tuhin Khare's user avatar
2 votes
0 answers
56 views

Understanding the nature of psychological defense system by artificial intelligence

Do you think psychological defense system, for example, repression, regression, reaction, formation, isolation, undoing, projection, introjection, sublimation, etc., could be created by artificial ...
Soheil Paper's user avatar
2 votes
0 answers
117 views

What is the difference between evolutionary game theory and meta-heuristics?

Here is a list of meta-heuristic algorithms Ant colony optimization, Ant lion optimizer, Artificial bee colony algorithm, Bat algorithm, Cat swarm optimization, Crow search algorithm, Cuckoo ...
DRV's user avatar
  • 1,673
2 votes
0 answers
102 views

How does Friend-or-Foe Q-learning intuitively work?

I read about Q-Learning and was reading about multi-agent environments. I tried to read the paper Friend-or-Foe Q-learning, but could not understand anything, except for a very vague idea. What does ...
Harris Pat's user avatar
2 votes
0 answers
119 views

Strong and Weak Dominance Table

I have this table, 2 agents and I want to find for each agent if any action is strongly or weakly dominated. This is the table: Now, i've found a solution but I'm not sure if it's correct. So for let'...
Georgio3's user avatar
1 vote
1 answer
133 views

Is neural fictitious self play violating off-policy theorem

I was reading the NFSP player from D. Silver, and I'm somewhat confused by the algorithm: In particular, given that we sample an action according to best response ($\sigma = \epsilon-\text{greedy}(Q)$...
Alberto's user avatar
  • 1,677
1 vote
2 answers
266 views

Can Alpha–Beta be used on symmetric zero sum games?

This question was asked in an AI exam. How would you answer such question?
Exprove's user avatar
  • 111
1 vote
1 answer
231 views

Shouldn't the utility function of two-player zero-sum games be in the range $[-1, 1]$?

In Appendix B of MuZero, they say In two-player zero-sum games the value functions are assumed to be bounded within the $[0, 1]$ interval. I'm confused about the boundary: Shouldn't the value/...
Maybe's user avatar
  • 461
1 vote
3 answers
166 views

What approaches are there to apply AI to global economic processes?

Today, AI is mainly driven by own-profit-oriented companies (e.g. Facebook, Amazon, Google). Admittedly, there's a lot of AI in the health sector (even in the public health sector) and there's a lot ...
Hans-Peter Stricker's user avatar
1 vote
2 answers
597 views

Why do iterative deepening search start from the root each iteration in the context of the minmax-algorithm?

Consider the graph below for an understanding on how IDS work. Now my question is: why do IDS start at the root every iteration, why not start at the previously searched depth in the context of minmax?...
steward's user avatar
  • 11
1 vote
2 answers
518 views

Would AlphaZero work just with a value network?

There is a nice post about the intuition why AlphaZero works. One of the advantages of using a policy network in the games where a perfect simulator is available (such as chess) is to save computation ...
Druudik's user avatar
  • 149
1 vote
1 answer
951 views

How exactly is Monte Carlo counterfactual regret minimization with external sampling implemented?

I have read many papers, such as this or this, explaining how external sampling works, but I still don't understand how the algorithm works. I understand you divide $Q$, which is the set of all ...
kpopgirl's user avatar
1 vote
1 answer
677 views

Optimal mixed strategy in two player zero sum games

I am currently studying game theory based on Peter Norvig's 3rd edition introduction to artificial intelligence book. In chapter 17.5, the two player zero sum game can be solved by using the $\textbf{...
calveeen's user avatar
  • 1,261
1 vote
1 answer
296 views

Compressing text using AI by sending only prediction rank of next word

Is there any effort made to compress text (and maybe other media) using prediction of next word and thus sending only the order number of the word/token which will be predicted on the client side i.e ...
sktguha's user avatar
  • 111
1 vote
1 answer
82 views

Can programs like AlphaGo be said to be means of dealing with computational intractability?

I mean this in the sense that Go is unsolvable but AlphaGo seems able to make choices that are consistently more optimal than a human player's choices. It is my understanding that Game Theory ...
DukeZhou's user avatar
  • 6,237
1 vote
0 answers
82 views

Examples of rationalizable AI

The marvelous book Game Changer: AlphaZero's Groundbreaking Chess Strategies and the Promise of AI gave rise to this question. It is - in my opinion - a perfect example of rationalizing a piece of AI ...
Hans-Peter Stricker's user avatar
1 vote
0 answers
70 views

Book/course recommendation on game theory application to multi-agent system (reinforcement learning)

Is there any great game theory book or course that discusses the application of game theory to modern reinforcement learning or multi-agent systems? Or a classic reference book that can help me get a ...
Maybe's user avatar
  • 461
1 vote
0 answers
44 views

AI for games which involve social intelligence. Games like warewolf where players must persuade, charm, threaten etc

I'm looking for any introductory/accessible reading on AI that can play games which involve social intelligence. Games like poker, where you might bait someone into overcommiting their hand or ...
Shiny_and_Chrome's user avatar
1 vote
0 answers
449 views

What is the size of 6-players no limit Texas holdem Poker?

What is the number of game states/information sets in 6-players, no limit, Texas Holdem? A year ago, Pluribus reached a super-human level in 6-players no limit Holdem Poker. I am interested in the ...
Cohensius's user avatar
  • 413
1 vote
1 answer
458 views

Find the expected reward in an expectimax-based dice rolling game?

I have this question that I'm kinda stuck on. It's a game scenario in which we set up an expectimax tree. In the game, you have 3 dice with sides 1-4 that you roll at the beginning. Then, depending on ...
Manny's user avatar
  • 21
1 vote
0 answers
100 views

Minimax algorithm with only partial visibility

I'm trying to implement the minimax algorithm with alpha beta pruning on a game that works like this: Player 1 plays (x1, y1). Player 2 can only see the x-value (x1) that Player 1 played (and not ...
SpiderManCity's user avatar
1 vote
0 answers
251 views

Is Monte Carlo tree search guaranteed to converge to the optimal solution in two player zero-sum stochastic games?

I'm aware that convergence proofs for Monte Carlo tree search exist in the case of deterministic zero sum games and Markov decision processes. I have come across research which applies MCTS to zero-...
markr3656's user avatar
1 vote
0 answers
47 views

Does Algorithmic Mechanism Design come under the field of AI?

I see many papers in AAMAS talk about artificial intelligence and mechanism design simultaneously. I was wondering, for the sake of being pedantic, is mechanism design could be classified under AI.
kosmos's user avatar
  • 121