Scribd Logo
Upload

Welcome to Scribd!

  • 295 views

    Cops and Robbers Presentation For Website

    Uploaded by

    api-260788629
    This document describes a game of cops and robbers played on a graph. It introduces the rules of the game and challenges the reader to determine who would win given any graph. It then presents an approach using a "metagraph" to model all possible game states. The document outlines an algorithm to iteratively remove losing positions from the metagraph until determining whether the cop or robber can force a win. Pseudocode is provided to implement this algorithm. Finally, it notes the metagraph can reveal optimal strategies for both players.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    Cops and Robbers Presentation For Website

    Uploaded by

    api-260788629
    295 views11 pages
    This document describes a game of cops and robbers played on a graph. It introduces the rules of the game and challenges the reader to determine who would win given any graph. It then presents an approach using a "metagraph" to model all possible game states. The document outlines an algorithm to iteratively remove losing positions from the metagraph until determining whether the cop or robber can force a win. Pseudocode is provided to implement this algorithm. Finally, it notes the metagraph can reveal optimal strategies for both players.

    Original Title

    cops and robbers presentation for website

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document describes a game of cops and robbers played on a graph. It introduces the rules of the game and challenges the reader to determine who would win given any graph. It then presents an approach using a "metagraph" to model all possible game states. The document outlines an algorithm to iteratively remove losing positions from the metagraph until determining whether the cop or robber can force a win. Pseudocode is provided to implement this algorithm. Finally, it notes the metagraph can reveal optimal strategies for both players.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    295 views11 pages

    Cops and Robbers Presentation For Website

    Uploaded by

    api-260788629
    This document describes a game of cops and robbers played on a graph. It introduces the rules of the game and challenges the reader to determine who would win given any graph. It then presents an approach using a "metagraph" to model all possible game states. The document outlines an algorithm to iteratively remove losing positions from the metagraph until determining whether the cop or robber can force a win. Pseudocode is provided to implement this algorithm. Finally, it notes the metagraph can reveal optimal strategies for both players.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 11

    A GAME OF COPS AND ROBBERS

    Adam Scarchilli

    Outline

    Rules of the game


    Challenge
    Approach
    Algorithm
    Pseudo-Code
    Bonus: Strategies

    Rules of the Game

    Pursuit game cop wants to catch the robber


    and robber wants to avoid the cop
    To play, make a graph with vertices and edges
    Cop chooses a vertex
    Robber chooses a vertex
    Cop starts
    Alternate turns moving along connected
    vertices
    Continue until:

    They are on the same vertex (cop catches robber)


    The cop gives up and the robber wins

    Challenge

    Solve the game:


    Suppose the cop and robber plays perfectly
    On a given graph, two outcomes:

    Cop win cop will win with perfect play


    Robber win robber will win with perfect play

    You give me a graph, I can tell you who will


    win

    But how to do in general?

    Approach

    Use a metagraph! every vertex is a game state

    game state answers 3 questions

    Whos turn to move (cop or robber)


    Where is the cop (what vertex)
    Where is the robber (what vertex)
    Ex. (C, 1, 2) means it is the cops turn to move, the cop
    is on vertex 1, and the robber is on vertex 2.

    If a move goes from one game state to another,


    they are connected by a directional edge in a
    digraph

    For this simple graph

    Heres the metagraph!!!

    Algorithm

    The secret work backwards!


    Start from positions where the robber is caught
    Get rid of those positions until you have a new
    graph where the robber no longer has the option
    to make those mistakes

    If the robber lands on the cop, get rid of the end node
    If the cop lands on the robber, also get rid of the
    second to last node (robber cannot make a bad
    move / lose the next turn)

    Repeat on the new graph. Stripping end vertices


    can create new end vertices. And so on.

    Algorithm

    After iteratively removing end states, two cases:

    Final Graph is empty cop win


    Final Graph is non-empty robber win

    Why? Graph is empty all bad robber moves are


    eliminated, he has no safe moves left

    Graph is non-empty robber simply stays on this


    final graph

    cop can never escape these cycles to find a winning


    path (otherwise removing end points would cut into
    the cycles via the escape path)

    Pseudo-Code

    While End nodes exist:


    For all end nodes:
    If the robber moved last:
    Delete the end node and all connections to it
    If the cop moved last:
    Delete the end node and all connections to it
    For all cop moves that goes to the end node:
    Delete the cop moves and all connections
    If final graph is empty:
    cop win
    Else:
    robber win

    Bonus: Strategies

    Can you show the best strategy?

    Cop win graphs:

    Cop quickest ways to win


    Robber list of moves to always evade capture

    Track how you removed vertices in the metagraph


    Following this sequence is the fastest way to win

    Robber win graphs:

    Final metagraph is not empty


    Just stay on that metagraph!

    You might also like