6
\$\begingroup\$

I am programming a game where there are 4 competitors (players) who have finished goods that they can then sell to given markets for which they have (at most a single) contracts for. Any finished goods is for a given market.

Turn order is important in the game as this will decide who sells first.

Scenario.

Turn order: Player #A, #C, #D, #B

The problem I'm having is I have no idea how to make the AI players aware of the following factors; they seem to need to know a lot of things which may impact on where to sell first.

For example, AI needs to know.

  1. Am I the only person who can sell to a given market? If so, that's fine -- sell all goods to market.

If not, do the following

  1. Who are my competitors for a given market and will I be able to sell first?

  2. If I sell in Market A, will I still get a chance to sell to Market B when turn order returns to me? (demand for items goes down for every sale and can bottom out)

Indeed, this is one strategy I'm wanting to employ -- sell to a given market because i he does not he might not get a chance to sell again when turn order returns to them.

  1. If I sell, should the AI go for most revenue per selling round.

Currently I am looking to order all markets for a given player based upon selling ability (who can sell first)

Basically an array of people who can sell for a given market based on player order.

These people then sell, and we reduce the array by one and repeat the process.

Whilst this solves some problems, it does not solve the bigger problem, which is the AI will just end up selling stuff in the order that of the Markets array; and not specifically to the ones where it is either advatangeous to do so, or will generate them the most money.

I am wondering, how do you design an AI to make coheriant, logical decisions about what when and why they would sell to a given market?

Sorry for the wall of text.

Many thanks

\$\endgroup\$
  • \$\begingroup\$ In addition to the answers below, taking a look through the king-of-the-hill tag over at PCG might not be a bad idea as well. \$\endgroup\$ – XNargaHuntress Apr 27 '15 at 12:34
9
\$\begingroup\$

The minmax tree method

You basically have the AI simulate every possible move it can make and every possible response by the other players for several turns in advance, and then pick the path which is most beneficial to it.

The advantages of this method is that it can usually deal very well with any changes to the gameplay because it only looks at the consequences of a move without having to consider why these consequences happened. You can also scale the difficulty very easily by setting the number of turns the AI calculates in advance.

The hardest thing about this algorithm is usually the rating function which determines what "most beneficial" means, but for an economy simulation it is surprisingly easy because you can usually express this in net-worth of the players (having more money and assets than the other players = good, having less = bad).

This method is very popular for games like Chess where you have a limited number of possible moves per turn, no randomness and no information hiding. According to your description your game seems to look like this. But you might be omitting some additional complexity.

When you have a very large number of possible moves, the decision tree becomes so wide that calculating more than one turn ahead takes too long even on a high-end computer.

When you have randomness or information hiding, you can either assume that the most likely event will always happen. Unfortunately this will greatly weaken the AI in case something unexpected happens instead. Or you can have the AI cheat. Have it know what will happen in advance by using the current random number generator state for the simulations and have it take any information into account it shouldn't actually have access to. This is very likely to make the AI frustrating to play against because it will soon become obvious to the player that the AI has an unfair advantage. Still, there is a large number of very successful games which make use of this technique.

The strategical rating method

This seems to be the method Jon is describing in his answer. In this method you evaluate all possible decisions the AI can make and have certain rules which rate the feasibility of the move based only on the current game situation.

Such rules could be "do not sell when the price is lower than average" or "do not buy when the other players have a lot of the same resource". The AI values all these factors by assigning relative scores to them and then makes the decision which has the best score.

This method requires to have a deeper understanding of the game as a whole because you need to define all the rules and ratings of when a decision is good or bad. This means the AI can not play any better than you could play the game. You can not increase the difficulty (except by cheating), you can only decrease it by making the AI take less rules into account. Hardcore gamers will soon find out how the AI works and find exploitable weaknesses. It also makes the strategy very fragile to changes. Any balance adjustments or new features will require to re-evaluate all AI rules to make sure they still provide good advise. And I hope you don't have an active modding community, because any new feature they throw at the AI will totally break it because it can not deal with things it doesn't know about.

But despite these weaknesses this method is still the most popular one for more complex games. In the 4X and RTS genre most AIs work like this.

\$\endgroup\$
  • 1
    \$\begingroup\$ Regarding strategical rating, one thing that can help a lot to keep players from 'gaming' the hard-coded AI strategies is to add some randomness. Have the strategies generate probability weights for which actions are likely to be best, but then choose the action randomly so as not to be predictable. This also provides one area where you can add a difficulty adjustment knob (by adding additional probability weight to the moves that are likely mistakes.) That said, some players actually enjoy a more predictable AI, as part of the game can be learning the patterns and how to beat them. \$\endgroup\$ – Dan Bryant Apr 27 '15 at 14:23
  • \$\begingroup\$ I'm probably going to lean towards AI has a "persona" as it might make things easier for me \$\endgroup\$ – zardon Apr 30 '15 at 20:13
  • 1
    \$\begingroup\$ I also reading up on the "Monte Carlo Tree Search" which might be another solution \$\endgroup\$ – zardon Apr 30 '15 at 20:28
2
\$\begingroup\$

(You have not specified a programming language or graphics API)

C# (some variable and method names are made-up, but are named to indicate their purpose)

public class Market
{
   ... //Existing stuff
   public int GetScore(Player player)
   {
      int score = 0; //0 == "better than doing nothing"
      if (this.Factor1.Helps(player)) score++; //there is excess demand!!
      if (this.Factor2.Helps(player)) score++; //there is insufficient supply!!
      if (this.Factor1.Hurts(player)) score--; //there is no demand (no margin)
      if (this.Factor2.Hurts(player)) score--; //there is too much supply (saturated)
      return score; //score might be negative
   }
}

and

public class Player
{
   ... //Existing stuff
   private Market findBestMarket()
   {
      Market bestMarket = null; //reset
      int bestScore = 0; //reset
      foreach (Market market in PlayersMarkets) //Check each of the player's markets
      {
         int score = market.GetScore(this); //Score the current market
         if ((bestMarket == null) ||    //If there is no "best" yet
            (score > bestScore))        //or if this one is better than the "best"...
         {
            bestMarket = market; //save for return
            bestScore = score; //save for score-keeping
         }
      }
      if (bestMarket == null)   //Should only happen
         throw new Exception(); //if PlayersMarkets is empty
      return bestMarket; //return the market with the best score
   }
}
\$\endgroup\$
  • 5
    \$\begingroup\$ This answer would benefit from a more theoretical explanation of the concepts behind this code, how it works, why it works, and what the strengths and weaknesses of this method are. \$\endgroup\$ – Philipp Apr 27 '15 at 8:21
  • \$\begingroup\$ +1 for "this comment adds something useful to the post" - No it didn't. It didn't add anything. It only pointed out that something needs to be added. If commenting every. single. line. of. code. isn't enough, feel free to click 'edit'. \$\endgroup\$ – Jon Apr 27 '15 at 8:50
  • 3
    \$\begingroup\$ @Jon I would argue that pointing out how something can be improved is useful. \$\endgroup\$ – Alex Apr 27 '15 at 10:51
  • \$\begingroup\$ @Jon instead of improving your answer I decided to write my own. \$\endgroup\$ – Philipp Apr 27 '15 at 11:43
  • 2
    \$\begingroup\$ I voted this answer up because I do like this approach, but no commenting every single line isn't the be-all-end-all of explanations. While those comments are appreciated, they still require that you read and grok the entire code listing in order to understand what it's doing, and that can be tl;dr with no introductory overview. It doesn't have to be long, just one or two sentences of "this approach does so and so. here's a code example:" \$\endgroup\$ – jhocking Apr 27 '15 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.