Graph Search:

The Silver Bullet of Symbolic AI and the Secret of AlphaGo Zero

ML Conference, December 2018

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", "_"]

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

Generic implementation

def breadth_first_search(root):
  closed_list = set()
  open_list = [root]
  while open_list:
    state = open_list.pop(0)
    # 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

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