Skip to content

Latest commit

 

History

History
598 lines (349 loc) · 6.48 KB

deck.md

File metadata and controls

598 lines (349 loc) · 6.48 KB

playing pacman

with

monte carlo 🌲 search

@danielepolencic & @ek_codes


80%


Chess Carcassone Hearthstone


Actual Scripts Scripts ? ? ?


...does it think for real?

...can I build one?


[fit] the challenge



400 positions after 2 moves

10,921,506 after 7 moves

avg game ~30 moves


not all moves are the same

sequence of moves



avg game ~150 moves

386,356,909,593 games with 2x2

19x19 - 101048 possible games



interesting because...


deterministic movements

simple to understand

real time

constrained space


[fit] hey computer,

[fit] what's your next move?

^ how does AI play cards? ^ cannot be brute force


brute force 💪

Heuristic

Neural networks


Brute force 💪

Heuristic

Neural networks


fast?

easy to implement?

skilled ai player?


fast

easy to implement?

skilled ai player?


fast

easy to implement

skilled ai player?


fast

easy to implement

skilled ai player


Brute force 💪

Heuristic

Neural networks


fast?

easy to implement?

skilled ai player?


fast

easy to implement?

skilled ai player?


fast

easy to implement

skilled ai player?


fast

easy to implement

skilled ai player


Brute force 💪

Heuristic

Neural networks


fast

easy to implement

skilled ai player


fast

easy to implement

skilled ai player


fast

easy to implement

skilled ai player


😩 😭


easy to code & smart,

please


another approach


pacman


fit


fit


fit


fit


fit


fit


fit


fit


🔗 of moves


[fit] more like a 🌲


fit


fit


fit


fit


fit


fit


fit


fit


fit


fit


fit


fit


fit


the next move for pacman is…


fit


fit


fit


fit


fit


fit


fit


fit


…and if pacman is distracted


fit


fit


fit


fit


💡 like a human!


recap


1. explore states

2. map winning/losing states

3. count


easy to implement?

skilled ai player?

fast?


coding involved:

1. movements

2. win/lose


easy to implement

skilled ai player?

fast?


easy to implement

skilled ai player

fast?


when should I stop?

how many children per node?

full 🌲 for every move?


fast ❌


unelss incremental


fit


fit


fit


fit


fit


fit


fit


fit


fit


fit


fit


fit


fit


fit


fit


the next move for pacman is…


fit


fit


fit


stop at any time

explore only promising branches

reuse previous states


fit


fit


fit


incremental is fast ✅


[fit] demo


📚 lessons learned


1. testing ai is hard


is it a bug or feature?

unit & integration test not enough


fit


fit


easy to inspect

extra tooling

still time consuming


2. ƛ functional


𝒻(state, message) -> state


function update(state, message) {
  switch(action.type) {

  case PACMAN_MOVES:
    /* ... */

  default:
  return state;
  }
}

const message = {
  type: PACMAN_MOVES,
  direction: 'left'
};

const state = {
  pacman: {x: 1, y: 0},
  red: {x: 0, y: 2}
};

no implicit state

no need to serialise classes

memoisation


3. time travel


const list_of_actions = [
  createAction_movePacman('left'),
  createAction_movePacman('right'),
  createAction_movePacman('right')
];

const initial_state = {
  pacman: {x: 1, y: 0},
  red: {x: 0, y: 2}
};

list_of_actions.reduce(update, initial_state);

fit


easier to debug

easier to reproduce bugs/features

easier to test


[fit] hungry for more?


thanks

@danielepolencic @ek_codes