Playing Pacman with Monte Carlo Tree Search

Writing algorithms for Artificial Intelligence is a lot of fun. You end up teaching your software how to move and learn in the environment and how to take actions to survive to obstacles and threats. But this is still software. How do you know your AI is not dumb as doorknobs? How do you test something that thinks and decides in its own terms? How can you be sure it is following your inputs in a strategic way?

Transcript

1. playing pacman with monte carlo ! search @danielepolencic & @ek_codes
5. ...does it think for real? ...can I build one?
6. the challenge
8. 400 positions after 2 moves 10,921,506 after 7 moves avg game ~30 moves
9. not all moves are the same sequence of moves
11. avg game ~150 moves 386,356,909,593 games with 2x2 19x19 - 101048 possible games
13. interesting because...
14. deterministic movements simple to understand real time constrained space
15. hey computer, what's your next move?
16. brute force ! Heuristic Neural networks
17. Brute force ! Heuristic Neural networks
18. fast? easy to implement? skilled ai player?
19. fast ❌ easy to implement? skilled ai player?
20. fast ❌ easy to implement ✅ skilled ai player?
21. fast ❌ easy to implement ✅ skilled ai player ❌
22. Brute force ! Heuristic Neural networks
23. fast? easy to implement? skilled ai player?
24. fast ✅ easy to implement? skilled ai player?
25. fast ✅ easy to implement ❌ skilled ai player?
26. fast ✅ easy to implement ❌ skilled ai player ✅
27. Brute force ! Heuristic Neural networks
28. fast ✅ easy to implement skilled ai player
29. fast ✅ easy to implement ❌ skilled ai player
30. fast ✅ easy to implement ❌ skilled ai player ✅
31. ! "
32. easy to code & smart, please
33. another approach
34. pacman
38. 2 1
39. 2 1
40. 2 1 3 2 1 3
41. 2 1 3 2 1 3
42. 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3
43. ! of moves
44. more like a !
45. 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3
46. 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3
47. 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3
48. 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3
49. 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3
50. 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3
51. 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3
52. 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3
53. 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3
54. 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3
55. 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3
56. 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3
57. 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3
58. the next move for pacman is…
59. 2 1
60. 2 1
61. 2 1 3 2 1 3
62. 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3
63. 2 1 3 2 1 3
64. 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3
65. 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3
66. 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3
67. …and if pacman is distracted
68. 2 1
69. 2 1 3 2 1 3
70. 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3
71. 2 1 3 2 1 3
72. ! like a human!
73. recap
74. 1. explore states 2. map winning/losing states 3. count
75. easy to implement? skilled ai player? fast?
76. coding involved: 1. movements 2. win/lose
77. easy to implement ✅ skilled ai player? fast?
78. easy to implement ✅ skilled ai player ✅ fast?
79. when should I stop? how many children per node? full ! for every move?
80. fast ❌
81. unelss incremental
83. 2 1
84. 0 0 1 0 0 1
85. 0 0 1 0 0 1 0 0 2
86. 2 1 3 2 1 3 0 0 1 0 0 1 0 0 2
87. 0 0 1 0 0 1 0 0 2 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1
88. 0 0 4 0 0 4 0 0 8 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1
89. 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 0 0 4 0 0 4 0 0 8 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1
90. 0 0 4 0 0 4 0 0 8 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1
91. 0 0 4 0 0 4 0 0 8 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1
92. 3 1 12 0 2 12 3 3 24 1 0 4 1 1 4 1 0 4 0 1 4 0 1 4 0 0 4 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1
93. 3 1 12 0 2 12 3 3 24 1 0 4 1 1 4 1 0 4 0 1 4 0 1 4 0 0 4 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1
94. 3 1 12 0 2 12 3 3 24 1 0 4 1 1 4 1 0 4 0 1 4 0 1 4 0 0 4 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1
95. 3 1 12 0 2 12 3 3 24 1 0 4 1 1 4 1 0 4 0 1 4 0 1 4 0 0 4 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1
96. 3 1 12 0 2 12 3 3 24 1 0 4 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1 1 1 4 1 0 4 0 1 4 0 1 4 0 0 4
97. the next move for pacman is…
98. 3 1 12 0 2 12 3 3 24 1 0 4 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1 1 1 4 1 0 4 0 1 4 0 1 4 0 0 4
99. 3 1 12 0 2 12 3 3 24 1 0 4 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1 1 1 4 1 0 4 0 1 4 0 1 4 0 0 4
100. 3 1 12 0 2 12 3 3 24 1 0 4 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1 1 1 4 1 0 4 0 1 4 0 1 4 0 0 4
101. stop at any time explore only promising branches reuse previous states
102. 3 1 12 0 2 12 3 3 24 1 0 4 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1 1 1 4 1 0 4 0 1 4 0 1 4 0 0 4
103. 3 1 12 0 2 12 3 3 24 1 0 4 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1 1 1 4 1 0 4 0 1 4 0 1 4 0 0 4
104. 0 2 12 0 1 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 1 4 0 1 4 0 0 4
105. incremental is fast ✅
106. demo
107. ! lessons learned
108. 1. testing ai is hard
109. is it a bug or feature? unit & integration test not enough
112. easy to inspect extra tooling still time consuming
113. 2. ƛ functional
114. (state, message) -> state
115. function update(state, message) { switch(action.type) { case PACMAN_MOVES: /* ... */ default: return state; } }
116. const message = { type: PACMAN_MOVES, direction: 'left' }; const state = { pacman: {x: 1, y: 0}, red: {x: 0, y: 2} };
117. no implicit state no need to serialise classes memoisation
118. 3. time travel
119. 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);
121. easier to debug easier to reproduce bugs/features easier to test
122. hungry for more? · http://aigamedev.com/open/coverage/mcts- rome-ii/ · https://chessprogramming.wikispaces.com/ Monte-Carlo+Tree+Search · https://pathak22.github.io/noreward-rl/
123. thanks @danielepolencic @ek_codes