Using AI to design board games • Hacker News Board

Re: Using AI to design board games

#21

Post by takeoutweight » Thu, Jan 05, 2012, 2:10 AM UTC

radarsat1 wrote: post #12

Interesting application of genetic algorithms. The weird thing about GA though, and any optimiser, is that you need an "error function" that you will us to determine when one solution is better than another. Presumably he designed an error function for "fun", and his GA system finds local minima within it. But this is what I mean by "weird thing": you have to come up with a quantification of what makes a game fun, an…

The problem of assigning a "fun value" to a game is an active area of research. Julian Togelius and Georgios Yannakakis are some of the big names looking at this topic right now.

One approach is to use tried-and-true statistical techniques to build models from user feedback. Often a player will be provided two variations of a game and asked which one was more fun. This input, combined with various other factors (how did the player perform? how many enemies were there in each version?) help construct some sort of classifier to automatically evaluate new game variations.

An alternate approach, which I explored during my Master's research on the topic, was to analyze existing levels in commercially released videogames to construct a model of fun from that, as opposed to considering subjective human feedback. I chose to analyse Super Mario Brothers. It turns out you can see a very characteristic pattern in how the difficult portions of the levels are arranged. This pattern of difficulty takes the form of a rhythmic interplay of difficult and easier portions, and can be nicely described in terms of Flow and the Yerkes-Dodson law. We used this a criterion for evaluating automatically generated levels as a part of a larger system.

The applications of this are pretty wide. Perhaps we could automatically evaluate web page interactions according to a certain model of fun to engage users? Perhaps we can detect when people are not having fun and automatically generate alternate designs?

Re: Using AI to design board games

#22

Post by xianshou » Thu, Jan 05, 2012, 2:18 AM UTC

The principle of subset contradiction (as in Yavalath, where you win by making four in a row but lose if you make three first) is extremely interesting, and it also seems like it can be applied in a fairly simple, atomic way to various types of rulesets. I wonder if a Monte Carlo ruleset search system could integrate higher-level rule change "principles" such as subset contradiction, and apply them as operations to existing rulesets...

Re: Using AI to design board games

#23

Post by radarsat1 » Thu, Jan 05, 2012, 2:43 AM UTC

Nvn wrote: post #18

radarsat1 wrote: post #12

Interesting application of genetic algorithms. The weird thing about GA though, and any optimiser, is that you need an "error function" that you will us to determine when one solution is better than another. Presumably he designed an error function for "fun", and his GA system finds local minima within it. But this is what I mean by "weird thing": you have to come up with a quantification of what makes a game fun, an…

In the comments the author of the article refers to a paper[1] that describes the system (Ludi) that they're using. They came up with 57 aesthetics criteria which they used on games played by humans and compared the scores on the criteria to the human judgements. Based on this they picked the 16 best criteria and generated games. The fitness function is a score based on the criteria after n amount of automated playth…

That is awesome. Thanks for pointing it out. Science!

Re: Using AI to design board games

#24

Post by jacques_chester » Thu, Jan 05, 2012, 4:54 AM UTC

radarsat1 wrote: post #12

Interesting application of genetic algorithms. The weird thing about GA though, and any optimiser, is that you need an "error function" that you will us to determine when one solution is better than another. Presumably he designed an error function for "fun", and his GA system finds local minima within it. But this is what I mean by "weird thing": you have to come up with a quantification of what makes a game fun, an…

A project I briefly explored was to develop an algorithmic model of "agency" in a roleplaying game, with the idea of taking existing plotline generation approaches and using the agency algorithm as a heuristic path-picker through the possible plotline alternatives.

Re: Using AI to design board games

#25

Post by cpeterso » Thu, Jan 05, 2012, 4:59 AM UTC

Not unrelated is Kevan Davis' Ludemetic Game Generator (2003), which randomly combines categories and mechanics from those at BoardGameGeek to create new (and largely useless) game ideas, with arbitrarily appropriate titles:

http://kevan.org/ludeme

Some of the random games sound more fun than others. ;)

  Game: "Indkub"
  Categories: Industry / Manufacturing, Comic Book.
  Mechanics: Set Collection, Hand Management.

  Game: "Ugplay"
  Categories: Prehistoric, Trains.
  Mechanics: Acting, Trading.

Re: Using AI to design board games

#26

Post by rndmcnlly0 » Thu, Jan 05, 2012, 6:09 AM UTC

wtracy wrote: post #10

_delirium wrote: post #8

This paper, "Automatic Design of Balanced Board Games" [2007] might be of interest for similar reasons: http://www.aaai.org/Papers/AIIDE/2007/AIIDE07-005.pdf

Thanks! I've been kicking around the idea of using evolutionary algorithms to test gameplay balance, and it's cool to see that someone else is already working on it.

Before you jump to evolutionary algorithms, note "The Problem with Evolution" section in the OP. This was written by a guy who knows what he's doing with evolution, and it's interesting to see him turning to MCTS given his previous success with evolution.

The gist is that games are fragile with respect to mutations (motivating the need for a search paradigm not based on gradualism). This fragility may not exhibit itself as strongly for the parameter tweaking involved in the balancing problem, but balancing quickly shades into general game design when you start to consider non-trivial tweaks.

Re: Using AI to design board games

#27

Post by rndmcnlly0 » Thu, Jan 05, 2012, 6:14 AM UTC

Jtsummers wrote: post #9

mjwalshe wrote: post #3

Hmm i recall Trillion Credit Squadron back in the 80s where the use of computers was almost required to play and being at the bleeding edge of Ai research would be useful

Thanks for providing the name, I've been trying to remember that story for a while now but my google-fu was weak and I couldn't recall any name involved (person, program or game). I think you're refering to Dr. Douglas Lenat's Eurisko program. He applied it to the game Trillion Credit Squadron and won two years in a row with fleets the other participants scoffed at. The first year he/Eurisko won by creating a largely…

I'm in grad school for AI right now as a result of reading about Eurisko as a kid. Though I haven't followed up on the greater vision, my thesis proposal a few years ago pitched the project of building a Eurisko-style discovery system for game design: http://users.soe.ucsc.edu/~amsmith/proposal/amsmith-proposal...

Also, the fact that I had a good experience playing an "academic" class character in Traveller during college was also an influence in deciding to go to grad school. I haven't seen this class in any other RPG.

Re: Using AI to design board games

#28

Post by rndmcnlly0 » Thu, Jan 05, 2012, 6:21 AM UTC

radarsat1 wrote: post #12

Interesting application of genetic algorithms. The weird thing about GA though, and any optimiser, is that you need an "error function" that you will us to determine when one solution is better than another. Presumably he designed an error function for "fun", and his GA system finds local minima within it. But this is what I mean by "weird thing": you have to come up with a quantification of what makes a game fun, an…

It's natural to question how someone can unproblematically pose a metric on the value of game rulesets (particularly without a generous helping of philosophy and psychology to back it up). However, pragmatically, it's not a silly thing to try. If there were game-design IDEs in the future, we'd like them to provide the equivalent of spell/grammar check -- if there was an alternate design with an edit distance of two away from the current design that scored dramatically better on some canned metric, it might be worth putting a human eye on that alternative design.

If you think of the error function as the combined output of a bunch of "obvious flaw" detectors instead of a "theory of fun", then speculative optimization where the initial conditions come from a human's design under consideration becomes a potentially interesting bit of design automation. Think of design rule checks in CAD with a bit of fuzziness and a default bias -- instead of saying just yes/no, it can say "X might be a better alternative according to the metrics you've enabled in the preference window, consider adopting some of its edits".

Re: Using AI to design board games

#29

Post by rndmcnlly0 » Thu, Jan 05, 2012, 6:26 AM UTC

takeoutweight wrote: post #21

radarsat1 wrote: post #12

Interesting application of genetic algorithms. The weird thing about GA though, and any optimiser, is that you need an "error function" that you will us to determine when one solution is better than another. Presumably he designed an error function for "fun", and his GA system finds local minima within it. But this is what I mean by "weird thing": you have to come up with a quantification of what makes a game fun, an…

The problem of assigning a "fun value" to a game is an active area of research. Julian Togelius and Georgios Yannakakis are some of the big names looking at this topic right now. One approach is to use tried-and-true statistical techniques to build models from user feedback. Often a player will be provided two variations of a game and asked which one was more fun. This input, combined with various other factors (how…

Here's my restatement of the statistical approach (correct me if I'm wrong):

Instead of proposing some metric for fun that is valid a-priori, we are going to look for the very grounded game-specific correlates of fun and optimize with respect to those. Satisfactorily capturing the entire fuzzy sense of human fun in a finite piece of code is silly, but cataloging the observed feedback for every popular combination of level elements (e.g. "goomba two blocks to the right of a coin block while the player has a fire flower") is both practical and useful for automating level design.

Re: Using AI to design board games

#30

Post by rndmcnlly0 » Thu, Jan 05, 2012, 6:33 AM UTC

eru wrote: post #15

radarsat1 wrote: post #12

Interesting application of genetic algorithms. The weird thing about GA though, and any optimiser, is that you need an "error function" that you will us to determine when one solution is better than another. Presumably he designed an error function for "fun", and his GA system finds local minima within it. But this is what I mean by "weird thing": you have to come up with a quantification of what makes a game fun, an…

Given enough money, you can outsource the error function to mechanical turk. Or to go more meta (and possibly cheaper): Make designing a good error function part of a meta GA-run, and let those functions be judged by comparing their judgements with human judgements.

Given the effort the play a game and the inter-subject noise in a numerical judgement, I think a better use of Mechanical Turk would be to ask the player to do some blame assignment. That is, instead of rating a game as 4-stars, they could perhaps give a thumbs up/down to particular rules or sets of rules in abstracted representation of the game.

This kind of feedback extracts several more bits of information from the player than a single rating (making better use of them). However, it breaks the applicability of an evolutionary algorithm which treats both artifacts and fitness evaluation as black boxes. If you use a search algorithm that was aware of how the game was built from components, I'm guessing that component-level feedback (being both more objective and more specific) could provide more informative pressure to drive the algorithm than the standard interactive genetic algorithm setup gets.