class: center, middle

Artificial Intelligence

Optimization for Games

Gerard Escudero & Samir Kanaan, 2019

.footnote[source ]

---

class: left, middle, inverse

Outline

• .cyan[The Problem]

• Gradient Descent

• Genetic Algorithms

• Examples

• References

---

The Problem

• Problem: setting parameters

• Example 1:

  • Strategy Game with diferent kind of units

  • Every unit have diferent attributes (attack, defense, life points)

  • All the units have to be useful

  • We need to balance them

• Example 2:

  • Game difficulty level adjustment

• Example 3:

  • Setting parameters of a Machine Learning algorithm

---

Example

.cols5050[ .col1[

• Problem: Strategy Game

  • 10 unit types

  • 3 attributes (attack, defense, life)

  • 20 possible values (1..20)

  • possible combinations will be $20^{3\times 10}$

  • .blue[testing all combinations is impossible] ] .col2[

• Solution:

  • Find a reasonably good solution in a limited time

  • .blue[Optimisation algorithms]

• .blue[The Curse of Dimensionality] .center[ source]

]]

---

The Problem in Optimization

.center[
source ]

• .blue[Objective function]: many minima/maxima

• Simplest methods get stuck in local minima

---

class: left, middle, inverse

Outline

• .brown[The Problem]

• .cyan[Gradient Descent]

• Genetic Algorithms

• Examples

• References

---

Gradient Descent

.center[
source ]

• Methafor: going down a mountain to the lowest point.

• Gradient (partial derivatives) gives the direction of steepest descent

---

Hyperparameter: Step Size

.blue[Step size (η)]: factor to the gradient (arrow length)

• Too small: progress will be sloooooow

• Too big: it may jump over minima or go back and forth

• Can be adaptive (decrease with iterations)

.center[
source ]

---

class: left, middle, inverse

Outline

• .brown[The Problem]

• .brown[Gradient Descent]

• .cyan[Genetic Algorithms]

• Examples

• References

---

Genetic Algorithm I

Given a problem $P$ with a solution space $S$, the main components are:

• .blue[Chromosome] (solution): collection of .blue[genes] (parameters)

• .blue[Population]: collection of chromosomes

• .blue[Fitness function]: scores how good is a solution

• .blue[Selection]: selects best chromosomes

• .blue[Crossover]: from 2 random chromosomes & a random point:

  • requirements: $2\times n$ parents for each $n$ new chromosomes

.center[]

---

Genetic Algorithm II

• .blue[Mutation]: change a value
  • Probability of mutation (<10%)
  • Random index
  • Random number to add or substract

.center[]

Algorithm:

1. Random Population
2. Compute fitness
3. Selection 
4. Crossover
5. Mutation
6. Go to step 2

---

Behavior

.center[]

---

class: left, middle, inverse

Outline

• .brown[The Problem]

• .brown[Genetic Algorithms]

• .cyan[Examples]

• References

---

Live Demo!

.blue[HTML_Genetic_Cars] in js:

.center[]

• web / github

---

Maze

.blue[Genetic Algorithm in Unity]:

.center[]

• github

---

Training Neural Networks

with backpropagation and evolution based learning in Unity:

.center[]

• Building a neural network framework in C#

• Mutation Project on Github.

• Backpropagation Project on Github.

---

class: left, middle, inverse

Outline

• .brown[The Problem]

• .brown[Genetic Algorithms]

• .brown[Examples]

• .cyan[References]

---

References

• Ian Millington. AI for Games (3rd edition). CRC Press, 2019.

• Rafael Matsunaga. Genetic Cars, github.

• Sebastian-Schuchmann. Genetic Algorithm in Unity.

• Kip Parker. Building a neural network framework in C#.

• Viktor Seč. Karl Sims - Evolving Virtual Creatures With Genetic Algorithms. 1994.

• Thomas Geijtenbeek. Flexible Muscle-Based Locomotion for Bipedal Creatures. 2013.