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
0
votes
0answers
23 views

Computing best response for imperfect-information extensive-form game

I have implemented the Counterfactual Regret Minimization (CFR) algorithm in recursive form. See for instance Algorithm 1 of An Introduction to Counterfactual Regret Minimization by Neller and Lanctot....
1
vote
0answers
28 views

How do you prove that minimax algorithm outputs a subgame-perfect Nash equilibrium?

At every node, MAX would always move to maximise the minimum payoff while MIN choose to minimise the maximum payoff, hence there is nash equilibrium. By using backwards induction, at every node, MAX ...
1
vote
1answer
48 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/...
3
votes
1answer
49 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 ...
1
vote
0answers
22 views

What should be a good playing strategy in this 2-player simultaneous game?

This is a bot making problem from here. I am detailing the problem. The picture above shows the initial configuration of the game. P1 represents player1 and P2 represents player2. A scotch bottle is ...
1
vote
1answer
19 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). ...
2
votes
0answers
23 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 ...
2
votes
0answers
19 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 ...
6
votes
1answer
105 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'...
2
votes
1answer
75 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 ...
4
votes
2answers
88 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?
2
votes
0answers
40 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 ...
5
votes
2answers
71 views

Perfect Information and Imperfect Information Games

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 ...
2
votes
2answers
68 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 ...
3
votes
3answers
379 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 ...
2
votes
0answers
53 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 ...
1
vote
0answers
115 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 ...
2
votes
0answers
80 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 ...
1
vote
2answers
146 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 ...
3
votes
0answers
45 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 (...
1
vote
0answers
43 views

How can/should I use AI to populate a game (in the game theory sense) from text input

I'm wanting to conduct game theoretic analyses of ongoing conflict situations (e.g. the US/North Korea negotiations; Syrian conflict; etc) as reported in the news media. I believe that AI may help me ...
1
vote
0answers
42 views

What to study for this simple poker game?

I'm a programmer with a background in mathematics, but I have no experience whatsoever with artificial intelligence/neural networks. I'd like to study it as a hobby, and my goal for now is to solve ...
1
vote
2answers
127 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?
4
votes
4answers
409 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?
4
votes
4answers
243 views

What if there's a game where all the AI people actually lived?

Imagine the fictitious scenario in a role playing game (RPG) where the non-playing characters (NPCs) within the RPG are conscious of their own surrounding and consider the developer to be god. The ...
2
votes
0answers
32 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'...
3
votes
1answer
165 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?
3
votes
1answer
82 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; ...
3
votes
1answer
187 views

RTS Construction Layout AI

So, I am trying to create an AI to handle the construction layout of a real time strategy game like Age of Empires II. The process has too many steps to be handled effectively by brute force, but also ...
1
vote
0answers
48 views

Mini (local) NN for Mobile?

I'm working on architecture for a game AI where, due to the nature of the game, the classical approach seems likely be sufficient to beat most humans--the endgame is tractable and traditional game-...
9
votes
1answer
2k views

A few doubts regarding the application of reinforcement learning to games like chess

I invented a chess-like board game. I built an engine so that it can play autonomously. The engine is basically a decision tree. It's composed by: A search function that at each node finds all ...
3
votes
3answers
429 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 ...
3
votes
2answers
2k 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 ...
3
votes
1answer
128 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'...
11
votes
4answers
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 ...
6
votes
3answers
913 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 ...
2
votes
0answers
67 views

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

For instance Strength/Size*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 ...
8
votes
1answer
239 views

Are there any other machine learning models apart from Reinforcement Learning and Q Learning to play video games?

OpenAI's Universe utilises RL algorithms and I have heard of some game-training projects using Q learning, but are there any others which are used to master/win games? Can genetic algorithms be used ...
1
vote
1answer
70 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 ...
6
votes
3answers
1k views

Board/Card Game AI - Questions concerning state/action space - Deep Reinforcement Learning

Ok, I now know how a machine can learn to play to play Atari games (Breakout): Playing Atari with Reinforcement Learning With the same technique it is even possible to play FPS games (Doom): Playing ...
7
votes
3answers
2k 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 ...
3
votes
1answer
551 views

How could Deep Blue possibly cheat?

On Wikipedia we can read: Kasparov accused IBM of cheating and demanded a rematch. IBM refused and retired Deep Blue. What was the accusation and how was Deep Blue allegedly able to cheat?
5
votes
1answer
156 views

Illustration of Von Neumann's Minimax theorem in games?

The Von Neumann's Minimax theorem gives the conditions that make the max-min inequality an equality. I understand the max-min inequality, basically ...