Return to Video

13-06 Single Player Game

  • 0:00 - 0:03
    Here's a game that we've seen before.
  • 0:03 - 0:07
    We call this a single-player deterministic game.
  • 0:07 - 0:09
    We know how to solve this.
  • 0:09 - 0:13
    We use the techniques of search through a state space--the problems solving techniques.
  • 0:13 - 0:18
    We draw a search tree through the state space,
  • 0:18 - 0:24
    and I'm going to draw the nodes like this with triangles rather than with circles.
  • 0:24 - 0:28
    In any position--in this position here--there are three moves I can make.
  • 0:28 - 0:32
    I can slide this tile, this tile, or this tile.
  • 0:32 - 0:36
    So I have 3 moves, and that gives me 3 more states.
  • 0:36 - 0:42
    I keep on expanding out the states going farther and farther down until I reach one
  • 0:42 - 0:49
    that's a goal state, and then I have a path through there that gets me to a solution.
  • 0:49 - 0:51
    What does it take to describe a game?
  • 0:51 - 0:58
    Well, we have a set of states S, including a distinguished start state S0.
  • 0:58 - 1:03
    We have a set of players P that can be our one player, as in this game, or two or more.
  • 1:03 - 1:10
    We have a function that gives us the allowable actions in a state,
  • 1:10 - 1:13
    and sometimes we put in a second argument,
  • 1:13 - 1:17
    which is the player, in that state-making action,
  • 1:17 - 1:21
    and sometimes it's explicit in the state itself whose turn it is to move.
  • 1:21 - 1:25
    We have a transition function that tells us the result of,
  • 1:25 - 1:29
    in some state, applying an action giving us a new state.
  • 1:29 - 1:34
    And we have a terminal test to say is it the end of the game.
  • 1:34 - 1:36
    That's going to be true or false.
  • 1:36 - 1:42
    Finally, we have terminal utilities saying that for a given state and a given player
  • 1:42 - 1:46
    there is some number which is the value of the game to that player.
  • 1:46 - 1:52
    In simple games that number is a win or a loss, a one or a zero.
  • 1:52 - 1:56
    Sometimes it's denoted as a +1 and a -1.
  • 1:56 - 2:00
    In other games there can be more complicated utilities
  • 2:00 -
    of you win twice as much or four times as much or whatever.
Title:
13-06 Single Player Game
Description:

Unit 13 06 Single Player Game.mp4

more » « less
Team:
Udacity
Project:
CS271 - Intro to Artificial Intelligence
Duration:
02:06
Amara Bot added a translation

English subtitles

Revisions