Games Theory

 

Games theory

games theory

In AI, we use games to model the problem and to find the best strategy for an agent (player). in game theory, we have a similar environment to planning (static / dynamic, deterministic / stochastic, observability) but unlike planning in games, we also have the agents (players) and they might play against each other or could also work together to win.

Games theory concepts:

  • Two-player game – the most basic game, each player plays his move at his turn. Each Player takes an Action using a Strategy based on his Payoff function and knowledge from the other Player’s Previous Actions (Perfect) and Payoff function (Complete)
  • Zero-sum games – the best move for Player A is the worst move for Player B.
  • Minimax tree – a minimax tree allows us to find the best strategy for a player in each state. First, we build a game tree with all possible states (each level is a player’s turn). The leaves are the final states, then we go bottom-up (propagate) wherein each level the player chooses the best action for himself: Player A chooses the maximum value and Player B chooses the minimum. Eventually, we can have the most reasonable action to perform for each player in each state and will be able to know from the beginning which player will win or if it will be a draw.
  • Nash equilibrium – a solution concept for non-cooperative, complete with 2+ players where no player gains from changing his strategy: “Amy is making the best decision she can, considering Will’s decision, while Will’s decision remains unchanged AND Will is making the best decision he can, considering Amy’s decision while Amy’s decision remains unchanged.”

In the cyber world, there are many game theories models to describe an attacker/ defender battlefield [2].

Tic tac toe is a great example of demonstrating game theory concepts [3]. Each level in the tree is an action of a player, and after the construction of the entire tree, each player has a strategy of what action to perform knowing the future results. Therefore, we have a sum zero game and a Nash equilibrium because if each player knows the best strategy, then we might end up with a tie or that one of the players has an advantage for starting first or second.

tictactoe-graph
tictactoe game graph

 

  1. Game Theory for Network Security –  Xiannuan Liang and Yang Xiao, Senior Member, IEEE Communications Surveys & Tutorials 2013
  2. Game theory with Tic Tac Toe

 

Leave a Reply

Your email address will not be published. Required fields are marked *