5 ms·

Using AI to design board games

107 points by chaddeshon 15y ago

unoti 15y ago
A section of the article says this: Raf describes two requirements for serendipity to occur: 1. Active searching: The designer should not simply wait for inspiration to strike, but should immerse himself in ideas and look for harmonies between them... It reminds me of one of my favorite quotes from Picasso: “That inspiration comes, does not depend on me. The only thing I can do is make sure it catches me working.” ― Pablo Picasso
mjwalshe 15y ago
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
- Jtsummers 15y ago
  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 stationary fleet that could take enough damage to survive long enough to destroy its opponent. It exploited a damage rule in the competition. The damaged party got to select which component/subsystem was damaged. Eurisko constructed a fleet with many small, useless components which could be individually destroyed without impacting the effectiveness of the crafts themselves. Edit: Reading more about it apparently the primary advantage was the shear number of craft. Essentially a fleet of kamikaze craft that could overwhelm the enemy. http://en.wikipedia.org/wiki/Douglas_Lenat http://en.wikipedia.org/wiki/Douglas_Lenat http://en.wikipedia.org/wiki/Eurisko http://en.wikipedia.org/wiki/Eurisko
  - mjwalshe 15y ago
    Yes that was what I was thinking of i was always struck by the fact the book (in 1980) had the line "a personal computer would be useful" Ironically Elite was a rip off of the basic starship combat rules in Traveller and i did try and write a game on our PDP 11/03 / VT55 using Traveler as a base.
  - rndmcnlly0 15y ago
    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-talk.pdf 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.
MichaelGagnon 15y ago
From the article: "Should the mantle of 'creator' lie with the program or the programmer?" Strangely enough, this was the exact dilemma that Clarissa faced in in Episode 29 of Clarissa Explains it All, "Poetic Justice," in which she developed a program that generated poetry. When her program's poetry won the school's contest, she decided to publicly relinquish her award to her computer. http://en.wikipedia.org/wiki/List_of_Clarissa_Explains_It_All_episodes#Season_3:_1992.E2.80.931993 http://en.wikipedia.org/wiki/List_of_Clarissa_Explains_It_Al...
- kiba 15y ago
  What an obscure reference to use. That show aired from 1991 to 1994, when I was a mere toddler.
  - deleted 15y ago
    [deleted]
  - zeteo 15y ago
    Wait ten more years, you'll also be able to use obscure references.
  - MichaelGagnon 15y ago
    As far as pop-culture goes, I think Clarissa still holds the cake for female programmer characters. Acid burn (from Hackers) is a close second...
    - Blocks8 15y ago
      Learn something new everyday -- Clarissa was a programmer! Loved that show!
    - alanfalcon 15y ago
      My winner is Veronica Mars's Mac whose scheme to get a new car was downright evil genius (scalable too, but she chose to limit herself). Of course, Burn was right, RISC changed everything, though not yet in desktop PCs.
_delirium 15y ago
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 http://www.aaai.org/Papers/AIIDE/2007/AIIDE07-005.pdf
- wtracy 15y ago
  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.
  - rndmcnlly0 15y ago
    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.
    - wtracy 15y ago
      Thanks for pointing that out. The project I was thinking of was going to be a tower defense game, and I wasn't planning on trying to develop any rules automatically. Rather, I was thinking in terms of using an evolutionary system to pick weapon and enemy strengths that lead to balanced gameplay. So, I would probably get away with it, but I'm wide open to different ideas.
radarsat1 15y ago
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, and _this_ is ultimately what will determine what kinds of solutions you come up with. Regardless of how the optimiser works, the error function is what the programmer is designing, and therefore the programmer is designing the space in which solutions will exist, so I would argue that any specific games are attributed to the programmer (or whoever designed the error function), and any specific game just happens to be one choice within the available search space. Unless you want to manually try every iteration and rate it from 1 to 10, this implies that it's possible to come up with a "funness" model of human game playing. That in itself is sort of a interesting thing, falling somewhere between philosophy and psychology, rather than computer science.
- eru 15y ago
  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.
  - ced 15y ago
    Why not go full Turk? Have a Turker suggest a new rule/modification. It will be paid for only if accepted by another, who must play N recorded moves of the game with a friend before passing judgment. Iterate. Disclaimer: I've never used MT. Is this possible?
  - rndmcnlly0 15y ago
    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.
shawnc 15y ago
Great thoughts and very well explained also - and neat to see BoardGameGeek get linked on HN - been a BGGer for many years.
dangd 15y ago
A friend of mine implemented the GA-generated game Yavalath for Android. You can find it on Android Market at https://market.android.com/details?id=boardgamer.yavalath https://market.android.com/details?id=boardgamer.yavalath. Yavalath has surprising depth, but it is no BattleField 3. It is nice to see BoardGameGeek listed on HN.
xianshou 15y ago
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...
cpeterso 15y ago
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 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.

107 points by chaddeshon 15y ago

unoti 15y ago

A section of the article says this: Raf describes two requirements for serendipity to occur: 1. Active searching: The designer should not simply wait for inspiration to strike, but should immerse himself in ideas and look for harmonies between them... It reminds me of one of my favorite quotes from Picasso: “That inspiration comes, does not depend on me. The only thing I can do is make sure it catches me working.” ― Pablo Picasso

mjwalshe 15y ago

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

Jtsummers 15y ago
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 stationary fleet that could take enough damage to survive long enough to destroy its opponent. It exploited a damage rule in the competition. The damaged party got to select which component/subsystem was damaged. Eurisko constructed a fleet with many small, useless components which could be individually destroyed without impacting the effectiveness of the crafts themselves. Edit: Reading more about it apparently the primary advantage was the shear number of craft. Essentially a fleet of kamikaze craft that could overwhelm the enemy. http://en.wikipedia.org/wiki/Douglas_Lenat http://en.wikipedia.org/wiki/Douglas_Lenat http://en.wikipedia.org/wiki/Eurisko http://en.wikipedia.org/wiki/Eurisko
- mjwalshe 15y ago
  Yes that was what I was thinking of i was always struck by the fact the book (in 1980) had the line "a personal computer would be useful" Ironically Elite was a rip off of the basic starship combat rules in Traveller and i did try and write a game on our PDP 11/03 / VT55 using Traveler as a base.
- rndmcnlly0 15y ago
  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-talk.pdf 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.

MichaelGagnon 15y ago

From the article: "Should the mantle of 'creator' lie with the program or the programmer?" Strangely enough, this was the exact dilemma that Clarissa faced in in Episode 29 of Clarissa Explains it All, "Poetic Justice," in which she developed a program that generated poetry. When her program's poetry won the school's contest, she decided to publicly relinquish her award to her computer. http://en.wikipedia.org/wiki/List_of_Clarissa_Explains_It_All_episodes#Season_3:_1992.E2.80.931993 http://en.wikipedia.org/wiki/List_of_Clarissa_Explains_It_Al...

kiba 15y ago
What an obscure reference to use. That show aired from 1991 to 1994, when I was a mere toddler.
- deleted 15y ago
  [deleted]
- zeteo 15y ago
  Wait ten more years, you'll also be able to use obscure references.
- MichaelGagnon 15y ago
  As far as pop-culture goes, I think Clarissa still holds the cake for female programmer characters. Acid burn (from Hackers) is a close second...
  - Blocks8 15y ago
    Learn something new everyday -- Clarissa was a programmer! Loved that show!
  - alanfalcon 15y ago
    My winner is Veronica Mars's Mac whose scheme to get a new car was downright evil genius (scalable too, but she chose to limit herself). Of course, Burn was right, RISC changed everything, though not yet in desktop PCs.

_delirium 15y ago

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 http://www.aaai.org/Papers/AIIDE/2007/AIIDE07-005.pdf

wtracy 15y ago
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.
- rndmcnlly0 15y ago
  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.
  - wtracy 15y ago
    Thanks for pointing that out. The project I was thinking of was going to be a tower defense game, and I wasn't planning on trying to develop any rules automatically. Rather, I was thinking in terms of using an evolutionary system to pick weapon and enemy strengths that lead to balanced gameplay. So, I would probably get away with it, but I'm wide open to different ideas.

radarsat1 15y ago

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, and _this_ is ultimately what will determine what kinds of solutions you come up with. Regardless of how the optimiser works, the error function is what the programmer is designing, and therefore the programmer is designing the space in which solutions will exist, so I would argue that any specific games are attributed to the programmer (or whoever designed the error function), and any specific game just happens to be one choice within the available search space. Unless you want to manually try every iteration and rate it from 1 to 10, this implies that it's possible to come up with a "funness" model of human game playing. That in itself is sort of a interesting thing, falling somewhere between philosophy and psychology, rather than computer science.

eru 15y ago
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.
- ced 15y ago
  Why not go full Turk? Have a Turker suggest a new rule/modification. It will be paid for only if accepted by another, who must play N recorded moves of the game with a friend before passing judgment. Iterate. Disclaimer: I've never used MT. Is this possible?
- rndmcnlly0 15y ago
  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.

shawnc 15y ago

Great thoughts and very well explained also - and neat to see BoardGameGeek get linked on HN - been a BGGer for many years.

dangd 15y ago

A friend of mine implemented the GA-generated game Yavalath for Android. You can find it on Android Market at https://market.android.com/details?id=boardgamer.yavalath https://market.android.com/details?id=boardgamer.yavalath. Yavalath has surprising depth, but it is no BattleField 3. It is nice to see BoardGameGeek listed on HN.

xianshou 15y ago

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...

cpeterso 15y ago

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 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.