Thomas Brower
United States
Rigby
Idaho
flag msg tools
Hello! First time poster here and I am looking for some help. I am currently working on a senior project for my bachelor's degree in which I am researching the mathematics behind board games. The main question I am going to be asking when approaching my project is, "What strategy will help me win most of the time?" Do you as designers find that a particular strategy in your game is 'broken' or 'unfair'? The ultimate goal for my project is to identify certain variables within a game and then run a computer program simulating thousands of plays on a particular game to see if a particular strategy yields the highest results. How do you identify 'variables' inside a game and how best do you go about assigning them?

If possible I am also looking to find published articles relating strategy checking on board games. If any of you have any information on how I can find those articles or if I could get pointed in the right direction that would be MOST helpful!

Any and all help would be appreciated! I am incredibly excited to research this as I am VERY passionate about board gaming!!! Thank you for all of your help!

-Thomas
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeremy Lennert
United States
California
flag msg tools
designer
Avatar
mbmbmbmbmb
I'm not aware of any research specifically about using computer tests to design better-balanced games; however, there is a good bit of research on trying to make computers play games better, which seems closely related.

Some things that spring to mind include...

AlphaGo - Google made headlines last year when their AI beat the human world champion at Go, a game which has historically been very challenging for computers to play well.

General Game Playing - This is the field studying how to make an AI that can learn and play new games (as opposed to most practical game-playing AIs, which are specially designed for one specific game). There are ongoing competitions to design better general-game-playing AIs.

Monte Carlo tree search - a popular technique used in general-game-playing AIs that uses a combination of "short-range" tree search to determine the immediate tactical effects of a move plus many randomized trials to estimate the long-term strategic benefit.

Hierarchical Portfolio Search (academic paper) - A recent technique used to make a fairly-impressive computer player for Prismata, which is a computer game but is very board-game-like

Going further back, there are some extremely powerful and well-understood AIs for playing some specific famous board games like Chess and Backgammon, though these techniques do not seem to generalize as easily as one might wish.



From your description of your intentions, I suspect you may be overestimating how good computers are at playing board games. For many popular games, it requires a substantial effort (weeks to years of skilled labor) just to create a computer program that can play one game at a level that humans would consider acceptable; and in some genres, we don't know how to do it at all. You talk about having a computer simulate thousands of plays to test out different strategies, but you could plausibly end up simulating millions of games just to teach the computer how to play competently in the first place.

Therefore, it could be very challenging to write a single computer program that can play a variety of games well enough to provide useful data on game balance. You will likely be stuck hand-crafting a specialized program for each game you want to study. (But if you want to try to do otherwise, do take a look at the general-game-playing stuff.)

But setting that aside...suppose you have a computer that can play your game of choice at a roughly-human skill level. That computer still isn't going to play the same as a human. There are likely to be strategies that are reasonable for a computer to execute, but unreasonable for humans--and vice versa. Even in board games where computers can beat humans, they often can't simulate humans.

So if your goal is to collect information on what strategies are unbalancing between human players, you might find that interpreting that data is very challenging, and the best interpretation may still leave large gaps in your knowledge.



But to give a more explicit answer to your specific question about identifying and assigning variables: I believe it is typical to create numerical parameters for your AI based on expert human knowledge of what is important in the specific game, start those parameters with the expert human's best guess, and then fine-tune them using a genetic algorithm that involves having the computer play against itself a large number of times.

For instance, if you're making an AI for Chess, you might talk to a bunch of humans who have played a bunch of Chess, and they'd tell you it's probably good to pay attention to how many pieces on each side (and what kinds, since certain piece are more valuable), putting rooks on open files, avoiding doubled pawns, keeping the king safe, etc.

Notice this list tells you almost nothing about how to play other games--even relatively similar games like checkers or arimaa.
4 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Pelle Nilsson
Sweden
Linköping
flag msg tools
designer
badge
Avatar
mbmbmbmbmb
I think it could be useful to simulate very simple games involving randomness (or small parts of less simple games) to calculate the probability of one strategy winning over another, or just the probability of some events in general. Because exact calculation of the probabilities is often prohibitively expensive (or just very difficult), especially when there are decks of cards involved or other unknown information about the game state. Could see room for some serious research be put into creating good methods/tools for that.

But that would assume problems where very simple ai is needed, ie obvious strategies, otherwise what Jeremy said applies.

Probably have a look at the related field called Game theory as well?
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeremy Lennert
United States
California
flag msg tools
designer
Avatar
mbmbmbmbmb
pelni wrote:
I think it could be useful to simulate very simple games involving randomness (or small parts of less simple games) to calculate the probability of one strategy winning over another, or just the probability of some events in general. Because exact calculation of the probabilities is often prohibitively expensive (or just very difficult), especially when there are decks of cards involved or other unknown information about the game state.

Sure. If there's no real strategy involved, then Monte Carlo simulations are quite useful.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Vincenzo Cappelleri
Italy
Padova
PD
flag msg tools
badge
Avatar
mbmbmbmbmb
Hi Thomas.
I would suggest you to get a look at the "Online Computation and Competitive Analysis" book (more info here: http://dl.acm.org/citation.cfm?id=290169) rather than pure Game Theory articles. I'm no expert on this field but my PhD advisor was very fond of it, so over the years I got a general knowledge of it.

I do agree with Jeremy on:

Antistone wrote:
suppose you have a computer that can play your game of choice at a roughly-human skill level. That computer still isn't going to play the same as a human. There are likely to be strategies that are reasonable for a computer to execute, but unreasonable for humans--and vice versa. Even in board games where computers can beat humans, they often can't simulate humans.


good strategies (using this word in the Game Theory acception) seldom look like "the right thing to do" for a human player.

Due to implementation complexity and potential computational onerosity, I'd suggest you to narrow the scope of your project to the analysis of a single turn, inspecting the "gain" in a sort of "return on investment" setting. You can easily develop simple AIs or simple markov chains producing a rather accurate result for that, while a full game simulation will likely end up being very far from the human ground truth you could be looking for.

Anyway: I find your endeavor very interesting, let us know your results.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Laura Creighton
Sweden
Göteborg
flag msg tools
Avatar
mbmbmbmbmb
http://www.onlamp.com/pub/a/onlamp/2004/09/30/AIforGameDev.h...
is well worth reading, especially if you think that a good dose of 'machine learning' is just what the project needs. It's not a difficult read.
Building a neural network means you don't have to stand outside and identify all the variables before you start writing your AI -- this is something which emerges.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Vincenzo Cappelleri
Italy
Padova
PD
flag msg tools
badge
Avatar
mbmbmbmbmb
I think he does not have a data set to train his <insert ML algorithm name here>. From what I gathered the whole point of games simulation is for data collection.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeremy Lennert
United States
California
flag msg tools
designer
Avatar
mbmbmbmbmb
lacreighton wrote:
Building a neural network means you don't have to stand outside and identify all the variables before you start writing your AI -- this is something which emerges.

Yes and no.

While making a Snapgammon AI, I read several of the early research papers about training a neural net to play Backgammon (which culminated in the first world-class Backgammon AI player), and one of the things they emphasized was that it is much easier for the neural net to learn how to play when you choose a "good" way of representing the input game state, so that the salient features are linearly independent.

For instance, I might have started by having an input that represents the number of pieces on a single space. But they instead created 5 inputs for that, representing:

- At least 1 piece on the space (binary on/off)
- At least 2 pieces on the space (binary on/off)
- At least 3 pieces on the space (binary on/off)
- At least 4 pieces on the space (binary on/off)
- Number of pieces above 4 on the space (variable-weight)

The first three of those ended up with very different connections to the hidden layer; it would have been very difficult to draw similar conclusions if they had all been combined into a single variable-weight input. (In Backgammon, 1 piece by itself can be attacked, but 2 pieces together are safe, so there's a big qualitative difference.)

For a neural network, you don't need to identify the high-level strategic features, but the method you choose for encoding the game state is still important and not necessarily obvious.

(To be fair, they were using pretty small neural networks, which probably makes efficiency more important than if you throw huge computational resources at the problem. It might be interesting to contrast this with AlphaGo, but I don't know as much about AlphaGo.)
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeremy Lennert
United States
California
flag msg tools
designer
Avatar
mbmbmbmbmb
vic_ita wrote:
I think he does not have a data set to train his <insert ML algorithm name here>. From what I gathered the whole point of games simulation is for data collection.

A typical way to train a game-playing AI is to have it play a very large number of games against itself, which doesn't require that you have any pre-existing data. It starts out playing randomly, but gradually improves over time.

Using data sets manually labeled by a human expert is often less effective than you would think; computers can't necessarily generalize in the way that a human pupil would, and even with expert players it's tough to ensure they aren't making errors.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Vincenzo Cappelleri
Italy
Padova
PD
flag msg tools
badge
Avatar
mbmbmbmbmb
Antistone wrote:
they emphasized was that it is much easier for the neural net to learn how to play when you choose a "good" way of representing the input game state


Absolutely true. But you will never get to a clever representation without actually "looking" at a representative data set. (And of course, without cross validating your guesses.)

Thus, as I said: I think the ML way is not viable for him, due to lack of data. (Moreover I'm pretty sure his project is for a game theory class, so ML would be sort of "cheating"...)
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeremy Lennert
United States
California
flag msg tools
designer
Avatar
mbmbmbmbmb
I suppose I'll also throw out that combinatorial game theory is a thing that might interest you (although most board games are not strictly combinatorial games).
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Vincenzo Cappelleri
Italy
Padova
PD
flag msg tools
badge
Avatar
mbmbmbmbmb
I wrote my last post while you sent yours.

Antistone wrote:

A typical way to train a game-playing AI is to have it play a very large number of games against itself, which doesn't require that you have any pre-existing data. It starts out playing randomly, but gradually improves over time.


True, but you must already have a good (linearly independent) set of features. These are likely to be the "variables" that he is looking for in the first place.

Quote:

Using data sets manually labeled by a human expert is often less effective than you would think; computers can't necessarily generalize in the way that a human pupil would, and even with expert players it's tough to ensure they aren't making errors.


I do agree. But you are gonna need a training data set both for a supervised or an unsupervised approach, in fact I never said anything about labeling the data set. I am merely pointing out that a basic one would be needed.
If such data set has to be built by an AI playing against itself and improving over time... Well I think the complexity of building such an AI is not so different from the complexity of building his originally proposed simulator.

Anyway, I guess this is going slightly off topic, forgive me! :)
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Greg
United Kingdom
flag msg tools
designer
Avatar
mbmbmbmbmb
I've sometimes used cut down simulations to work on my games. Full simulation of a game is a hard problem for lots of the reasons described in this thread and wouldn't be an efficient way to go about developing a game.

That being said I've done things like writing a bit of script for 404: Law Not Found that simulated random setup, calculated the number of moves needed to win and generated statistics for how often a character would enter each room if they were all moving by the most efficient path.

That couldn't meaningfully play the game and even calling it AI would be a push, but it was a useful thing to do because it helped me to understand how the difficulty of objectives in the game were modified by which rooms they required (higher traffic ones being harder to access).

In terms of a strategy being 'broken' or 'unfair', that tends to be fairly woolly thinking. The real question is whether there's a strategy that's diminishing the game - for instance by ensuring that a player who's the beneficiary of a particular random event will always win or by being so effective that the game has no interesting choices.

To an extent it doesn't matter if a strategy is dominant if all of the interesting parts of the game can be expressed through that strategy. Consider how bizaare it sounds to say something like "Ach, not another strategy involving taking the other player's pieces, every chess player does that."

I'm not sure what you mean by identifying variables within a game. Some examples come to mind:

There are values that I might vary as a game designer. In Scandinavia and the World: A Heap of Trouble I might want to vary whether the penalty for speaking with Finland in play is one or two coins. Or how many cards Russia makes a player draw. It tends to be fairly late in the day before I'm tinkering with things trying to get these values exactly right.

There are events that are particularly critical. For instance in Wizard's Academy I'm aware that the initial two level 1 disasters shuffled in the deck will have a strong impact on the character of the early and middle game. When I was considering changes and tests I'd want to consider how they'd impact games of types defined by these critical events.

You could also be talking in the computer science sense about the necessary set of values required to define the state of the game. For a game of any complexity that's going to be immense. I think this is where you might run into problems: For a game to be deep enough for there to be what people would think of as different strategic approaches, it will also probably be too complicated to easily simulate.

Also being able to demonstrate that a particular strategy leads to victory a certain percentage of the time isn't as meaningful as you might think. It could be that you can show that 'big money' wins 20%
of Dominion games and that's more than any other named strategy - but it misses the point. That looking at the initial board state you should be able to pick a best strategy for the set of cards available rather than commiting to a strategy before the start of the game and aiming for the one with the best win rate overall.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Laura Creighton
Sweden
Göteborg
flag msg tools
Avatar
mbmbmbmbmb
Well, AI for Game Development -- the book I linked to earlier, isn't only about Neural Nets and Machine Learning. At it is not a hard or long read. And comes with working code, which is always nice ...
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Front Page | Welcome | Contact | Privacy Policy | Terms of Service | Advertise | Support BGG | Feeds RSS
Geekdo, BoardGameGeek, the Geekdo logo, and the BoardGameGeek logo are trademarks of BoardGameGeek, LLC.