Visualising Game Trees with D3.js

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?

Join me in this talk as we build an AI for Pac-Man leveraging Monte Carlo Tree Search. With the help of D3.js we'll verify the correctness of the algorithm and enter in the mind of the machine.

Transcript

1. visualising game !s with D3.js @danielepolencic
2. i ❤ strategy games
4. how does it know it's a good move?
5. it's brute force !
6. almost
7. let's get started
8. the game
10. what's your move?
19. state looks like a !
20. you ! and "
21. monte carlo ! search
22. 1. expansion 2. selection 3. simulation 4. backpropagation
23. 1. expansion 2. selection 3. simulation 4. backpropagation
24. 1. expansion 2. selection 3. simulation 4. backpropagation
25. 1. expansion 2. selection 3. simulation 4. backpropagation
27. expand
30. ! Erase and Rewind !
31. select
34. simulate
36. ghost 0 - pacman 0 matches played: 1
37. backpropagate
38. 0 0 1
39. 0 0 1 0 0 1
40. ! one more time !
41. select
42. 0 0 1 0 0 1
43. 0 0 1 0 0 1
44. expand
45. 0 0 1 0 0 1
46. ! baby one more time !
47. select
48. 0 0 1 0 0 1
49. 0 0 1 0 0 1
51. simulate
52. ghost 0 - pacman 0 matches played: 2
53. backpropagate
54. 0 0 1 0 0 1 0 0 1
55. 0 0 2 0 0 1 0 0 1
56. 0 0 2 0 0 2 0 0 1
57. ! again & again !
58. ghost 1 - pacman 0 matches played: 3
59. ghost 2 - pacman 0 matches played: 5
60. ghost 2 - pacman 1 matches played: 11
61. ghost 2 - pacman 1 matches played: 21
62. ghost 3 - pacman 1 matches played: 34
63. ghost 5 - pacman 2 matches played: 67
64. ghost 15 - pacman 9 matches played: 823
65. ghost 45 - pacman 92 matches played: 3177
66. 0 0 2 0 0 2 0 0 1
67. 0 0 2 0 0 2 0 0 1
68. 0 0 3 0 0 5 0 0 1 0 0 2 0 0 1 0 0 1
69. 1 1 5 2 1 11 1 0 2 1 0 5 0 1 2 1 0 4 1 0 2 0 0 1 1 0 1 0 1 1 1 0 1
70. 3 3 13 6 3 25 3 2 10 3 0 12 0 1 2 3 0 11 1 0 2 2 0 8 1 0 1 0 1 1 1 0 2 1 0 5 1 0 1 0 2 4 1 0 1 1 0 1 1 0 4 0 1 1 0 1 2 0 1 1 1 0 2 0 0 1 1 0 1 2 2 7
71. 3 3 13 6 3 25 3 0 12
72. 11 3 89 18 11 156 7 8 67
73. 27 11 239 40 44 695 13 33 456
74. you lost?
77. 27 11 239 40 44 695 13 33 456
78. demo
79. learnings
80. 1. testing is hard
81. 2. scary algorithms ain't scary anymore
82. 3. immutability & redux ftw
83. UPDATE STORE #1 RENDER VIEW PLAYER MOVES UPDATE STORE #2 TURN MOVE WINNER ACTIONS SELECT EXPAND SIMULATE FEEDBACK AI ENGINE
84. Immutability FEL made x many 31st of March
85. 4. playing chess against a pc !
87. thanks
88. @danielepolencic