1 of 9

week 6:

​

Search methods for games human - machine

2 of 9

Game algorithm : human - machine

​

  • The algorithm consists of an initial state “Q0”, and a shift “T” you can take 2 values : M = machine o H = human .
  • 1ª It asks the question : “¿Q0 is the goal?”
    • 1.1 If true, then: "Win the machine" or "Win the human" or is in "Draw"
    • 1.2 But the question is asked : “¿T = H?”
      • 1.2.1 If true, then: "Play the human" and generates a new state Q1.
      • 1.2.2 Otherwise, "Play the machine" and generates a new state Q1.
  • 2ª Finally, assign : “Q0 = Q1”
  • 3ª Back to the point1.

​

​

3 of 9

Game machine strategies

  • Nondeterministic:

You should choose one of the possible moves, but randomly.

  • First the best:

Of all the possible moves, one must choose the best, that you get the optimum value of the evaluation function.

  • Min-Max:

Of all the best plays of the opponent, you should choose the worst, that give you minimum profit.

  • Best utility difference:

You should choose the play, which generates the best value of the difference between the moves of the machine and the human.

4 of 9

Algorithm Min-Max

  • 1. It generates all nodes in the tree until a terminal state..
  • 2. Calculate the value of the utility function for each relevant terminal condition (positive in case of winning, neutral in case of tie, negative if they lose).
  • 3. Go up one level at evaluations, starting at the base when the opponent turn, this will select an option that takes you to the worst start (for our point of view), so when our turn will choose THE BEST.

​

​

5 of 9

Example of the algorithm Min-Max

6 of 9

Example of the algorithm Min-Max

7 of 9

Example of the algorithm Min-Max

8 of 9

Algorithm Min-Max with poda alfa beta

  • Poda alfa beta is a search algorithm, which reduces the number of nodes in a tree evaluated by the algorithm Min-Max.
  • There are 2 threshold values​​: alpha and beta, alpha represents the lower limit on the value that maximizes a node can be assigned, while the beta value represents the upper limit on the value that minimizes a node can be assigned.

9 of 9

Example poda alfa - beta