Graph Search:
The Silver Bullet of Symbolic AI and the Secret of AlphaGo Zero
Oliver Zeigermann / @DJCordhose
Knowledge Representation
Find a way to encode the maze to make it accesible for a search algorithm
terrain = [
["_", "R", "_", "_"],
["B", "_", "B", "_"],
["_", "_", "B", "_"],
["B", "_", "G", "_"]
]
https://colab.research.google.com/github/djcordhose/ai/blob/master/notebooks/ai/Search.ipynb
Simple, stack based implementation
def depth_first_search(state, closed_list=[], path=[]):
if state in closed_list:
return None
closed_list = closed_list + [state]
if is_robot_win(state):
return path
for move, next_state in expand_robot(state):
new_path = path + [move]
res = depth_first_search(next_state, closed_list, new_path)
if res:
return res
https://colab.research.google.com/github/djcordhose/ai/blob/master/notebooks/ai/Play.ipynb
Generic implementation
def breadth_first_search(root):
closed_list = set()
open_list = [root]
while open_list:
state = open_list.pop(0)
closed_list.add(state)
# simplfied, needs a bit more information
if is_robot_win(state):
return construct_path(state)
to_visit = [x for x in expand(state) \
if x not in closed_list and \
x not in open_list]
# accounts for breadth first style
open_list = open_list + to_visit
https://colab.research.google.com/github/djcordhose/ai/blob/master/notebooks/ai/Search.ipynb
Admissible Search Heuristics
Search, diagonal allowed
Manhattan (non-admissible):
length 16.24
Euclidean (admissible):
length 15.07
Chess Computers have defeated humans because
Cray X-MP
Supercomputer (1982)
x 100.000 =
Titan 5 im Gamer PC (2017)
Wrap Up
Search is omnipresent in AI
- Path finding is dominated by variants of A*
- Chess can be solved using tweaked Alpha-Beta-Search
- For a high branching factor and/or no good heuristic use Monte Carlo Methods
- Monte Carlo Tree Search is an advanced Monte Carlo Method
- Alpha(Go) Zero uses a variant of MCTS together with Supervised Deep Learning and CNNs
- AlphaGo Zero beats all known Go players
Graph Search: The Silver Bullet of Symbolic AI and the Secret of AlphaGo Zero
Oliver Zeigermann / @DJCordhose
http://bit.ly/mlconf-search