Game Theory Introduction

Study Notes

Game Theory and Adversarial Search

Competitive environments with conflicting goals lead to adversarial search problems, often referred to as games.
Mathematical game theory views any multiagent environment as a game if the impact of each agent on others is significant, regardless of cooperation or competition.

Characteristics of Games in AI

Games in AI are usually deterministic, turn-taking, two-player, zero-sum games of perfect information.
These games have deterministic, fully observable environments with two agents taking alternating actions, resulting in equal and opposite utility values.

Examples of Games

Chess is a zero-sum game, where one player's win (+1) implies the other player's loss (-1).
Games, unlike toy problems, are challenging due to their complexity.

History of Game Playing in AI

Chess was one of the first tasks undertaken in AI, with early attempts by Konrad Zuse, Claude Shannon, Norbert Wiener, and Alan Turing in the 1950s.
Since then, there has been steady progress in the standard of play, with machines surpassing humans in checkers and Othello, and being competitive in many other games.
Go is an exception, where computers perform at an amateur level.

Challenges in Game Playing

Games have an enormous search tree, making it infeasible to calculate the optimal decision (e.g., chess has an average branching factor of 35 and games often go to 50 moves).
Games require making decisions under time constraints, and inefficiency is severely penalized.
Game-playing research has led to innovative ideas on optimizing time usage.

Description

Game theory is a branch of economics that views multiagent environments as games, where the impact of each agent on the others is significant. In AI, games are usually of a specialized kind, involving deterministic, turn-taking, and two-player scenarios.