AI - lesson 07

Francesco Arrigoni

4 November 2015

Adversarial search

Is usually employed in situations called games, in which there are multiple agents that interact together in a strategic way
For example in the game of chess we play against another player, and so our moves can be represented by a tree

There are different kind of games:

Perfect information games: we completely know the status of the game
Imperfect information games:

Another distinction is:

Deterministic games: There are no randomness factors
Chance games: there are elements of chance for example rolling dices or drawing cards.

examples

An example of perfect information and deterministic game is chess,
An imperfect and deterministic game is battleship
A perfect information based on chance is backgammon, or gioco dell'oca, or Monopoly
An imperfect information and chance game is poker or cards games.

For this time will focus of Perfect information and deterministic games like chess.

We have two players: Max and Min,
They are playing in turns,
Max will play first

An initial state is an initial configuration of the game.

Tic Tac Toe

Max: X Min: O

Initial state:

|| ---|---|--- || ||

We can define a __function "player(s)" that given a state will return which is the next player

$\text{PLAYER}(s)\in {max,min}$
$\text{ACTIONS}(s)= {a_1,a_2,...}$
$\text{RESULT}(s,a)=s'$
$\text{TERMINAL-TEST}(s)={yes,no}$

Next we define a utility function

$\text{UTLITY}(s,p)\in R$

We consider zero-based games, in which the utility of the two players in a final state are always summing up to zero $\text{UTILITY}(s,\text{MAX})+\text{UTILITY}(s,\text{MIN})=0$

For example X|O|O ---|---|--- |X| || $\text{RESULT}$Will give no as a result

While X|O|O ---|---|--- |X| ||X

$\text{RESULT}$Will give yes as a result While $\text{UTILITY(s,MAX}$Will give -1 as a result And $\text{UTILITY(s,MIN}$Will give +1 as a result

minimax

Is an algorithm for solving game trees

The root is called "MAX" node because t corresponds to MAX's turn
All children of MAX are called MIN nodes for the same reason
The third row contains the terminal nodes, and the number associated to every node is the utility for max to be in that node.

The minimax algorithm is based on the idea of a minimax value for each node, that represents:

The utility for max of being in (reaching) that node assuming that the other players will play optimally from that node to the end of the game

The general rule for calculating the minimax value is the following:

The minimax value of a terminal node is the utility of MAX
The minimax value of a MIN node is the minimum of the minimax value of the children
The minimax value of a MAX node is the maximum of the minimax value of the children

The minimax algorithm

Build all the game tree
Starting from the bottom we have to back-up the minimax value to the upper nodes.
Knowing the minimax value of all the children of a node, we can calculate the value of a node.

The minimax value can be minimized building a tree in a depth first fashion.

The problem of a possible cutoff strategy is that not completing the tree, we don't have terminal nodes, and i need an evaluation function

Cutoff strategy

Usually in chess or checkers i can cut-off the tree at a given level, but i can not do so at a random level

An option is implementing a quiescence evaluation function that tells us if a certain level is stable, otherwise we continue

lesson_07.md 3.5 KB História Raw