5 ms·

First draft of the new Artificial Intelligence and Games textbook available now

124 points by togelius 9y ago

CameronBanga 9y ago
I know it's a draft, but it's kinda annoying to have a big watermark of DRAFT over every page. I don't know if a better way to do it, but really makes it tough to jump in and commit to giving a read through.
jonbaer 9y ago
I would like to find books which pertain to just this problem alone (build order planning) ... "Another sub-problem of the wider StarCraft (Blizzard Entertainment, 1998) playing problem is build order planning. The problem here is in which order to build certain improvements to the player’s base and in which order to research certain technology, a complex planning problem at a considerably higher level of abstraction than micro-battles. Here, Weber et al have data-mined logs of existing StarCraft (Blizzard Entertainment, 1998) matches to find successful build orders that can be applied in games played by agents."
- jbpetersen 9y ago
  Now you've got me curious how much people have experimented with making AIs play "incremental" games where there's literally nothing but build order planning.
- yorwba 9y ago
  I think the literature on instruction scheduling might also be relevant for build order planning. You have a set of things to build (= instructions to execute) in the shortest amount of time, using the available production facilities (= execution units). Except in most games you can build additional factories, which doesn't really have an equivalent in CPUs.
  - thomasmarcelis 9y ago
    An additional difficulty is that the fastest way to achieve a build/goal often means you are weak/exposed at crucial moments in the game
  - philipov 9y ago
    > which doesn't really have an equivalent in CPUs. But it does have an equivalent in scalable cloud infrastructure, where you can literally download more RAM, cores, etc.
  - posterboy 9y ago
    > in most games you can build additional factories You can't just buy addition execution units? Sure there are limiting factors - in games as well.
    - yorwba 9y ago
      Which scheduler automatically inserts instructions to add more ALUs to its CPU? ;)
      - posterboy 9y ago
        Well, I did take a step back from the instruction pipeline analogy, but it's still covered by operations research and mathematical optimization. The cost of waking a sleeping CPU core is perhaps comparable to the cost of building a factory in-game. Whereas, building a ton of factories that can't be saturated by the incoming cash money is comparable to building a superscalar processor architecture that can't be saturated by the cache memory.
- mysterydip 9y ago
  I wonder if Goal-Oriented Action Planning would be a fit here: http://alumni.media.mit.edu/~jorkin/goap.html http://alumni.media.mit.edu/~jorkin/goap.html Ultimate goal being to destroy the opponent, different build orders meet that goal, scouting could show which direction the opponent is moving, and action plan adjusted to counter or take advantage of a weakness.
- dgant 9y ago
  How to efficiently achieve build goals is itself a mostly solved problem. See BOSS by Dave Churchill. The catch is that "can I build this without dying in the process" is an almost completely unsolved problem. Even "can my opponent just kill me now" is currently only solved by fairly crude approximation. Without being able to evaluate that statically we're nowhere near evaluating it over the course of a build order, accounting for incomplete information and multiple possible responses. In general, Starcraft is tricky because very small differences in unrelated concerns can cause wild swings in expected outcome. Compare a Terran wall-in that blocks zealots vs. one with a zealot-sized gap. A few pixels of space -- a pathfinding concern -- radically impacts build order concerns. Come check out the current state-of-the-art (and lots of earlier stage work as well) at http://twitch.tv/sscait http://twitch.tv/sscait
deepnet 9y ago
Togelius is pure mental (in a good OOTB way) his evo-devo HyperNEAT approach to problems intractable to random-walk SGD learning learning leaps over snares and pitfalls, bypasses cul-de-sacs and avoids oubliettes -traversing the whole search space by a sort of teleportation - a fast global search. Backprop can then refine the most efficient net architectures. Curiously some evolve structures akin to LSTM units.
nishnik 9y ago
From one glance I see that it doesn't covers neural network architecture or it's not taking about RL agents. What this book is about?
- otoburb 9y ago
  You may have been looking at an earlier (private?) draft revision of the guidebook that had those sections omitted. The draft book that is linked shows RL discussed in Sections 2.6 (pp. 75-79) and 3.3.2 (pp. 122-125), while Neural Networks are briefly covered in Section 2.5.1 (pp. 62-74) with a note about DeepMind's DQN RL agent on p. 91.
  - nishnik 9y ago
    Thank you

124 points by togelius 9y ago

I know it's a draft, but it's kinda annoying to have a big watermark of DRAFT over every page. I don't know if a better way to do it, but really makes it tough to jump in and commit to giving a read through.

jonbaer 9y ago

I would like to find books which pertain to just this problem alone (build order planning) ... "Another sub-problem of the wider StarCraft (Blizzard Entertainment, 1998) playing problem is build order planning. The problem here is in which order to build certain improvements to the player’s base and in which order to research certain technology, a complex planning problem at a considerably higher level of abstraction than micro-battles. Here, Weber et al have data-mined logs of existing StarCraft (Blizzard Entertainment, 1998) matches to find successful build orders that can be applied in games played by agents."

jbpetersen 9y ago
Now you've got me curious how much people have experimented with making AIs play "incremental" games where there's literally nothing but build order planning.
yorwba 9y ago
I think the literature on instruction scheduling might also be relevant for build order planning. You have a set of things to build (= instructions to execute) in the shortest amount of time, using the available production facilities (= execution units). Except in most games you can build additional factories, which doesn't really have an equivalent in CPUs.
- thomasmarcelis 9y ago
  An additional difficulty is that the fastest way to achieve a build/goal often means you are weak/exposed at crucial moments in the game
- philipov 9y ago
  > which doesn't really have an equivalent in CPUs. But it does have an equivalent in scalable cloud infrastructure, where you can literally download more RAM, cores, etc.
- posterboy 9y ago
  > in most games you can build additional factories You can't just buy addition execution units? Sure there are limiting factors - in games as well.
  - yorwba 9y ago
    Which scheduler automatically inserts instructions to add more ALUs to its CPU? ;)
    - posterboy 9y ago
      Well, I did take a step back from the instruction pipeline analogy, but it's still covered by operations research and mathematical optimization. The cost of waking a sleeping CPU core is perhaps comparable to the cost of building a factory in-game. Whereas, building a ton of factories that can't be saturated by the incoming cash money is comparable to building a superscalar processor architecture that can't be saturated by the cache memory.
mysterydip 9y ago
I wonder if Goal-Oriented Action Planning would be a fit here: http://alumni.media.mit.edu/~jorkin/goap.html http://alumni.media.mit.edu/~jorkin/goap.html Ultimate goal being to destroy the opponent, different build orders meet that goal, scouting could show which direction the opponent is moving, and action plan adjusted to counter or take advantage of a weakness.
dgant 9y ago
How to efficiently achieve build goals is itself a mostly solved problem. See BOSS by Dave Churchill. The catch is that "can I build this without dying in the process" is an almost completely unsolved problem. Even "can my opponent just kill me now" is currently only solved by fairly crude approximation. Without being able to evaluate that statically we're nowhere near evaluating it over the course of a build order, accounting for incomplete information and multiple possible responses. In general, Starcraft is tricky because very small differences in unrelated concerns can cause wild swings in expected outcome. Compare a Terran wall-in that blocks zealots vs. one with a zealot-sized gap. A few pixels of space -- a pathfinding concern -- radically impacts build order concerns. Come check out the current state-of-the-art (and lots of earlier stage work as well) at http://twitch.tv/sscait http://twitch.tv/sscait

deepnet 9y ago

Togelius is pure mental (in a good OOTB way) his evo-devo HyperNEAT approach to problems intractable to random-walk SGD learning learning leaps over snares and pitfalls, bypasses cul-de-sacs and avoids oubliettes -traversing the whole search space by a sort of teleportation - a fast global search. Backprop can then refine the most efficient net architectures. Curiously some evolve structures akin to LSTM units.

nishnik 9y ago

From one glance I see that it doesn't covers neural network architecture or it's not taking about RL agents. What this book is about?

otoburb 9y ago
You may have been looking at an earlier (private?) draft revision of the guidebook that had those sections omitted. The draft book that is linked shows RL discussed in Sections 2.6 (pp. 75-79) and 3.3.2 (pp. 122-125), while Neural Networks are briefly covered in Section 2.5.1 (pp. 62-74) with a note about DeepMind's DQN RL agent on p. 91.
- nishnik 9y ago
  Thank you