Challenge an opponent in a PyRat game

Project – Session 6

  • Combinatorial game theory
  • Computing winning positions in a game

Combinatorial game theory

Playing a game can be seen as a graph of configurations

  • Exploring this graph (arena) can be done using a strategy
  • A strategy is a function that, given a configuration, returns the next action

Computing winning positions in a game

The goal is to reach a winning configuration

  • First, identify configurations that are winning

Computing winning positions in a game

The goal is to reach a winning configuration

  • Then, extend to all configurations that allow you to reach a winning configuration in a single action

Computing winning positions in a game

The goal is to reach a winning configuration

  • Extend to all configurations that allow you to reach a previously found configuration in a single action

Computing winning positions in a game

The goal is to reach a winning configuration

  • Continue this process until saturation to identify the winning region
  • In other configurations, the opponent can win or force a draw

Computing winning positions in a game

Beware of complexity

Recap of the session

Main elements to remember

  • Games theory can be used to compute winning positions in a multi-player game

  • There are many sorts of games (simultaneous, perfect information, etc.) $\rightarrow$ check the articles

  • A strategy is a function that, given a configuration, returns the next action

  • A strategy determines how to explore the game’s arena

  • The goal is to reach a winning configuration

  • This can be done iteratively to identify the winning region

  • Other approaches exist (e.g., based on heuristics) to reduce the complexity

Recap of the session

What’s next?

Practical activity (~2h30)

Face an opponent

  • Think of your own strategy
  • Check the tournament page
  • Draw inspiration from the articles or invent something new!

Tournament

  • Monday 16th, 16:45
  • For fun and glory!
  • Submit your AI before Friday 13th, 23:59

After the session

  • Review the articles of the session
  • Check your understanding with the quiz
  • Complete the practical activity

Evaluation

  • Final presentation of your strategy
  • Check the project page for details