This edition of our developer diary is brought to you by Coleman Charlton, lead designer for Catan Online. Here, we focus on the AI in Catan Online.

A large portion of the resources for the development of Catan Online went into the artificial intelligence (AI) for the computer players. This AI is used for Catan: The Computer Game (the single-player version of Catan Online), as well as for players in Catan Online when human players drop out or are unavailable.

The Catan Online AI uses the “General Revenue” strategy: The AI player tries to maximize its resource production while increasing its victory point total. Most of this article will discuss this strategy and its development for Catan Online.

The Most Attractive Intersection
The general revenue strategy attempts to maximize resource production. So, it is important to have a parameter that reflects the relative resource production potential of each intersection. To that end, we have two basic definitions:

Production value of a hex: The number of times out of 36 that the hex is likely to produce (e.g., if a hex’s production number is 3 or 11, its production value is 2; if a hex’s production number is 5 or 9, its production value is 4, etc.). Production value of an intersection: The sum of the production values of the adjacent hexes.

An intersection’s production-value provides its base “attractiveness” to an AI player. However, a number of other factors affect the overall “attractiveness” of an intersection to a specific AI player. For example:

Can the AI player build a settlement on the intersection? If so, the intersection is an “open” intersection for that player. If not, the “attractiveness” of the intersection is zero. Does the AI player have a shortage of some of the resources produced by that intersection? If so, the intersection is more attractive to the AI player. Is the intersection a port? If so, the intersection is more attractive to the AI player. How many roads would the AI player have to build to reach the intersection? The further away an intersection is, the less attractive it is to the AI player.

Once an AI player calculates the attractiveness of all of his open intersections, he can determine his “most attractive intersection.” In general, the AI player will try to build roads to connect to its most attractive intersection, and it will try to build a settlement there when possible.

An AI Player’s Turn
During its turn, an AI player follows this procedure:

• Determine building project: The AI player decides what it wants to build next.
• Trade: If the AI player does not have the resources required for its building project, it tries to trade for the resources it needs.
• Build: If possible, the AI builds its building project. Otherwise, it ends its turn.
• Repeat: If the AI successfully built its building project, it repeats the steps above.

Selecting a Building project
If it already has the required resources, an AI player’s building project is a settlement on its most attractive intersection or a city or a road along the shortest route to its most attractive intersection. Otherwise, the building project is chosen from a list of priorities based upon factors like:

• The resources held
• The distance to its most attractive intersection
  Trading

If an AI player does not have all of the resources needed to build its building project, it will try to trade for the resources it needs. First, the AI player classifies each resource it holds as being one of three types:

• Required: The resource is needed to complete the building project.
• Ambivalent: The resource is not required, but two or less of a resource of the same type would be enough to complete a port trade (i.e., 4:1, 3:1, or 2:1).
• Tradable: The resource is not required and is not ambivalent.

If the AI player has some non-required resources, it will attempt to trade for a required resource. It will offer tradable resource first, and then ambivalent resources. If unsuccessful, it will try and trade for an ambivalent  resource. Then, if it has the ambivalent resources required for a port trade, it will port trade for a required resource.

Under certain conditions, the AI player will offer 2:1 and 3:1 trades if it is unsuccessful with 1:1 offers. In addition, if offers from other players meet certain similar criterion, the AI player will accept those offers.

Emergency Situations
The normal priorities for building projects can be superseded if certain emergency situations arise, for example:

• The building project can be a road if a Longest Road competition arises.
• The building project can be a development card if a Largest Army competition arises.
• The building project can be a development card if the AI player’s hand size gets too large, and the resources for the current building project are not available after trading is attempted.
• The building project is a city if all 5 settlements are in play.

Other AI Elements
There are a number of other elements that have to be handled by an AI:

• Where to set up initial settlements and roads: This is driven by an evaluation of the most attractive intersection values.
• Where to place the robber and who to take a resource from: This is driven by evaluating a number of factors:
  • Victory point totals
  • Resources known to be held by opponents
  • Intersection production-values
  • Positions of the opponents’ settlements/cities.
• When to play a development card: There are individual criterion for each type of development card.

Other AI Strategies
There are three other AI strategies that were not implemented, but which may be included in future upgrades and releases:

• The Expansion Strategy: The AI player focuses on building roads, Longest Road, and settlements.
• The Concentration Strategy: The AI player focuses on cities, dev cards, and Largest Army.
• The Adaptive Strategy: At the beginning of the game, the AI player chooses a strategy based on overall yield probabilities of the resource types. The AI player chooses the expansion strategy if hills and forest dominate or the concentration strategy if fields and mountains dominate. Otherwise, the AI player chooses the general revenue strategy.