Answers.Body: <p>Catan is actually a much more complicated game than the simple rules would suggest, and an <em>exact</em> solution is probably beyond the scope of current AI techniques.</p>
  
  <p>Monte Carlo Tree Search or Expectiminimax techniques <em>seem</em> like they could help, but are intended for games of perfect information. Catan is not a game of perfect information (the development cards are hidden), and also has a phase that occurs <em>without</em> a regular turn sequence (trading). </p>
  
  <p>To solve Catan properly, I think you're going to need both algorithms for solving POMDPs (like CFR+), <em>and</em> algorithms for negotiation (like <a href="http://u.cs.biu.ac.il/~sarit/data/articles/An%20Automated%20Diplomacy%20Paper.pdf" rel="nofollow noreferrer">Kraus' Diplomat</a>). I'm not certain that these have been combined before in formal analysis, so this might actually be a good PhD thesis for someone.</p>
  
  <p>That said, you can probably get a good player using self-play techniques, because Catan has randomization, and a relatively small set of moves, like <a href="https://en.wikipedia.org/wiki/TD-Gammon" rel="nofollow noreferrer">Backgammon</a>. These may or may not offer simple rules about how-best to play the game. Your friends are right to think about this as, at root, an ML problem. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-27T21:16:01.937Z
Answers.Text: Is it not inaccurate to say that the game has imperfect information? You can keep track of what development cards the other players have, by paying attention to their yields and expenses, could you not?
Answers.UserDisplayName: Krrrl
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-27T22:28:38.583Z
Answers.Text: @Krrrl You can keep track of how _many_ cards they have, but the cards are drawn randomly from a deck, and then concealed in players' hands. You can track how many cards of each kind have been played, and so you can _guess_ at what a card in someone's hand might be, based on that and on what they might be trying to buy or not. However, since you can't know for sure until the card is played, this is a game of imperfect information (that's the definition).
Answers.UserDisplayName: John Doucette
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-27T23:26:07.997Z
Answers.Text: I know the definition, but I am still arguing that since both die roll and settlement location is known at all times, you can infer what cards are in the other players hands at all time.
  Example: If exactly one turn has passed - where the value rolled was 6 - then you know that players with settlements on a "6" hex has received development cards for that area, lets say brick. If none of those players proceed to build something that requires brick that turn, you now know that their hand contains 1 brick, and so on. 
  Could it be that we are talking about different versions of Catan?
Answers.UserDisplayName: Krrrl
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-27T23:49:50.383Z
Answers.Text: @Krrrl It sounds like you have confused resource cards with development cards. Resource cards are awarded when dice are rolled. Development cards are purchased, and drawn face down from a shuffled deck. They are present in the base game, and all expansions.
Answers.UserDisplayName: John Doucette
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-28T00:24:15.930Z
Answers.Text: Ah, indeed I have! I also completely forgot about the variety of development cards(non-victory points ones). I concur with your statement about imperfect information, my apologies!
Answers.UserDisplayName: Krrrl
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-23T15:27:15.190Z
Answers.LastActivityDate: 2019-10-23T15:27:15.190Z
Answers.UserDisplayName: John Doucette
Answers.Body: <p>Historically, the non-ML approach would be an <a href="https://en.wikipedia.org/wiki/Expert_system" rel="nofollow noreferrer">expert system</a>.  This is typically a rules-based decision system, falling under the umbrella of <a href="https://en.wikipedia.org/wiki/Symbolic_artificial_intelligence" rel="nofollow noreferrer">symbolic AI</a>. </p>
  
  <p>These systems can have strong utility in limited contexts, but are generally "brittle" in that parameters not previously defined or accounted will produce no-compute or weak utility. Because the rules of a game are fully definable, the main concern is utility, which relates to the degree to which the game has been solved.</p>
  
  <p>Informing a <a href="https://en.wikipedia.org/wiki/Heuristic" rel="nofollow noreferrer">heuristic</a> system in this case requires analysis of the game in in the sense of game theory and combinatorial game theory, since Catan involves both imperfect information and combinatorial elements.  The complexity is high indeed, not only per imperfect information, branching factors, stochasticity, players > 2, but, as you note, the game board itself has a very high number of potential configurations, so solving the game is presumed to be extremely difficult to impossible.  (Possibly <a href="https://en.wikipedia.org/wiki/NEXPTIME" rel="nofollow noreferrer">NEXPTIME</a> if finite and undecidable otherwise.)</p>
  
  <p>The paper <a href="http://homepages.inf.ed.ac.uk/alex/papers/cig2014_gs.pdf" rel="nofollow noreferrer">Game strategies for The Settlers of Catan</a> suggests that the game tree for Catan is not surveyable b/c the options for trade negotiation in natural language aren't bounded:</p>
  
  <blockquote>
    <p>One response to this is to develop a symbolic model consisting of heuristic strategies for playing the game. Developing
    such models potentially has two advantages. First, a symbolic
    model can in principle lead to an interpretable model of human
    expert play ... Second, a symbolic model can provide
    a prior distribution over which next move is likely to be
    optimal...</p>
  </blockquote>
  
  <p>The paper mentions this second part to relation to machine learning, where "the posterior distribution over optimal actions acquired through training improves on the baseline prior distribution."  </p>
  
  <p>Especially where the game is unsolved and intractable, machine learning has demonstrated strong utility for an increasing number of games, so it is unlikely not to be an optimal component for truly strong play.  However, such a system can be a combination of ML and <a href="https://en.wikipedia.org/wiki/Domain_knowledge" rel="nofollow noreferrer">domain specific knowledge</a>, such as in <a href="https://en.wikipedia.org/wiki/Search_algorithm#For_virtual_search_spaces" rel="nofollow noreferrer">informed search</a>.</p>
  
  <p>The <a href="https://pdfs.semanticscholar.org/0ef6/7eac64e0d7ee2d68abf3976751940616aab9.pdf" rel="nofollow noreferrer">Optimizing UCT for Settlers of Catan</a> goes into this in detail, and also provides reference to prior work.</p>
  
  <p>If your primary requirement is strong utility, some form of machine learning is likely optimal.  But it can be fun to attempt to solve games and cobble together sets of heuristics. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-26T01:23:38.470Z
Answers.Text: Nice answer. I'm not sure about the claim of NEXPTIME though. I can easily see how it is in NP, but apart from the Natural Language component, it's not clear to me that we can be sure about the hardness of the game.
Answers.UserDisplayName: John Doucette
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-26T18:52:13.507Z
Answers.Text: @JohnDoucette Yeah, I was just making a guess based on [Constraint Logic](https://erikdemaine.org/papers/CL_Complexity2008/paper.pdf) for an imperfect information team game (here "team" b/c player >2, which can result in coalitions.)  I suspect proving it would be daunting indeed, and it doesn't even show up on this wiki chart of [hardness of popular games](https://en.wikipedia.org/wiki/Game_complexity#Complexities_of_some_well-known_games)!
Answers.UserDisplayName: DukeZhou
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-25T23:48:21.873Z
Answers.LastActivityDate: 2019-10-26T19:49:28.217Z
Answers.LastEditDate: 2019-10-26T19:49:28.217Z
Answers.UserDisplayName: DukeZhou
Answers.Body: <p>From the way you have phrased your question one can derive a couple of strong assumptions which simplify the problem tremendously and make it feasable:</p>
  
  <ol>
  <li>We do not look for an agent being able to play the game but only an evaluation of settlement options (no other agents to be considered)</li>
  <li>The evaluation of settlement options is static (i.e. does not change over time) and is independent of other settlements</li>
  </ol>
  
  <p>From that two simple ideas come to my mind: </p>
  
  <p><strong>1. the ML approach</strong>
  Look at historical game data and see which settlement options led to a win. So basically look at tuples of (X,y) with X being something like (W8, C2, O6) meaning that the settlement give access to wood with an 8, clay with a 2 and ore with a 6. And y indicating a win or loss. 
  To make it a bit dynamic you could differentiate between initial settlements (being placed at the beginning) and the ones during the game. So for each of these two categories you would derive basically a score for the possible settlements. </p>
  
  <p>If you can compute all the possible combinations you will not even need ML since you can simply run the math once and then look it up. Might be doable in this case as the assumptions mentioned above simplify the problem a lot (compared to fully "solving" the game). Thinking through the possible combinations for a given settlement location (selecting 3 fields with A possible resources and B possible numbers) will quickly give you an idea about that. </p>
  
  <p><strong>2. The classy symbolic approach</strong>
  What comes to my mind right away is linear programming as it offers a convenient way to model the strategic aspects you have mentioned. You could develop a target function to maximize using scores for different resources and numbers (e.g. you could give clay higher importance than wool). Besides that constraints can capture additional aspects of game strategies like "always make sure to have access to clay" or "do not settle where the 3 resources are the same" etc. </p>
  
  <p>My very first idea to model this is using decision variables like X_(i,j) with X being 0 or 1, i representing the resources out of {clay, wood, ..., desert} (side note: do not forget the water and different ports here) and j modelling the numbers out of {2,...12}. The constraints would need to model the fact that you need to select 3 of those X_(i,j) for every settlement. </p>
  
  <p>If you want to calculate this for a given game you would need to feed the model the possible settlement options based on the layout of that specific game. Then run the optimization and it gives you the best settlement option (i.e. the 3 feasable X_(i,j) maximizing your goal function).  </p>
  
  <p>Qua definition you need to bring in game knowledge for this approach. And probably talking to someone who is really good at the game would help to understand what matters. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-26T11:03:42.867Z
Answers.LastActivityDate: 2019-10-26T11:03:42.867Z
Answers.UserDisplayName: Jonathan
Body: <p>Is it possible to calculate the best possible placements for settlements in <a href="https://en.wikipedia.org/wiki/Catan" rel="nofollow noreferrer">Catan</a> without using an ML algorithm?</p>
  
  <p>While it is trivial to simply add up the numbers surrounding the settlement (highest point location), I'm looking to build a deeper analysis of the settlement locations. For example, if the highest point location is around a sheep-sheep-sheep, it might be better to go to a lower point location for better resource access. It could also weight for complementary resources, blocking other players from resources, and being closer to ports.</p>
  
  <p>It seems feasible to program arithmetically, yet some friends said this is an ML problem. If it is ML, how would one go about training, as the gameboard changes every game?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-10-23T08:30:05.400Z
Comments.Text: Could you be a little clearer on your definition of "best"? There are a few choices, but ones suitable for analysis usually focus on a precisely-defined measure. If your measure is "most likely to win the game ultimately" then that is a hard problem and there are lots of dependencies - critical is how the agent you are deciding for and the other players intend to play the game. Often an assumption of optimal play throughout is used, but is hard to define for games with greater than 2 players.
Comments.UserDisplayName: Neil Slater
Tags: <ai-design><game-ai><game-theory><combinatorial-games><symbolic-ai>
Title: How to calculate the optimal placements for settlements in Catan without an ML algorithm?
UserDisplayName: acj11507
ThreadText: # How to calculate the optimal placements for settlements in Catan without an ML algorithm?
  
  (Asked by: username_0 on 2019-10-23)
  
  Is it possible to calculate the best possible placements for settlements in [Catan](https://en.wikipedia.org/wiki/Catan) without using an ML algorithm?
  
  While it is trivial to simply add up the numbers surrounding the settlement (highest point location), I'm looking to build a deeper analysis of the settlement locations. For example, if the highest point location is around a sheep-sheep-sheep, it might be better to go to a lower point location for better resource access. It could also weight for complementary resources, blocking other players from resources, and being closer to ports.
  
  It seems feasible to program arithmetically, yet some friends said this is an ML problem. If it is ML, how would one go about training, as the gameboard changes every game?
  
  **Tags:** ai-design, game-ai, game-theory, combinatorial-games, symbolic-ai
  
  > **Comments:**
  > **username_1**: Could you be a little clearer on your definition of "best"? There are a few choices, but ones suitable for analysis usually focus on a precisely-defined measure. If your measure is "most likely to win the game ultimately" then that is a hard problem and there are lots of dependencies - critical is how the agent you are deciding for and the other players intend to play the game. Often an assumption of optimal play throughout is used, but is hard to define for games with greater than 2 players.  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_2 on 2019-10-23. Score: 4
  
  Catan is actually a much more complicated game than the simple rules would suggest, and an *exact* solution is probably beyond the scope of current AI techniques.
  
  Monte Carlo Tree Search or Expectiminimax techniques *seem* like they could help, but are intended for games of perfect information. Catan is not a game of perfect information (the development cards are hidden), and also has a phase that occurs *without* a regular turn sequence (trading).
  
  To solve Catan properly, I think you're going to need both algorithms for solving POMDPs (like CFR+), *and* algorithms for negotiation (like [Kraus' Diplomat](http://u.cs.biu.ac.il/~sarit/data/articles/An%20Automated%20Diplomacy%20Paper.pdf)). I'm not certain that these have been combined before in formal analysis, so this might actually be a good PhD thesis for someone.
  
  That said, you can probably get a good player using self-play techniques, because Catan has randomization, and a relatively small set of moves, like [Backgammon](https://en.wikipedia.org/wiki/TD-Gammon). These may or may not offer simple rules about how-best to play the game. Your friends are right to think about this as, at root, an ML problem.
  
  > **Comments:**
  > **username_3**: Is it not inaccurate to say that the game has imperfect information? You can keep track of what development cards the other players have, by paying attention to their yields and expenses, could you not?  
  > **username_2**: @username_3 You can keep track of how _many_ cards they have, but the cards are drawn randomly from a deck, and then concealed in players' hands. You can track how many cards of each kind have been played, and so you can _guess_ at what a card in someone's hand might be, based on that and on what they might be trying to buy or not. However, since you can't know for sure until the card is played, this is a game of imperfect information (that's the definition).  
  > **username_3**: I know the definition, but I am still arguing that since both die roll and settlement location is known at all times, you can infer what cards are in the other players hands at all time. Example: If exactly one turn has passed - where the value rolled was 6 - then you know that players with settlements on a "6" hex has received development cards for that area, lets say brick. If none of those players proceed to build something that requires brick that turn, you now know that their hand contains 1 brick, and so on.  Could it be that we are talking about different versions of Catan?  
  > **username_2**: @username_3 It sounds like you have confused resource cards with development cards. Resource cards are awarded when dice are rolled. Development cards are purchased, and drawn face down from a shuffled deck. They are present in the base game, and all expansions.  
  > **username_3**: Ah, indeed I have! I also completely forgot about the variety of development cards(non-victory points ones). I concur with your statement about imperfect information, my apologies!  
  
  ---
  
  ### Answer by username_4 on 2019-10-25. Score: 2
  
  Historically, the non-ML approach would be an [expert system](https://en.wikipedia.org/wiki/Expert_system). This is typically a rules-based decision system, falling under the umbrella of [symbolic AI](https://en.wikipedia.org/wiki/Symbolic_artificial_intelligence).
  
  These systems can have strong utility in limited contexts, but are generally "brittle" in that parameters not previously defined or accounted will produce no-compute or weak utility. Because the rules of a game are fully definable, the main concern is utility, which relates to the degree to which the game has been solved.
  
  Informing a [heuristic](https://en.wikipedia.org/wiki/Heuristic) system in this case requires analysis of the game in in the sense of game theory and combinatorial game theory, since Catan involves both imperfect information and combinatorial elements. The complexity is high indeed, not only per imperfect information, branching factors, stochasticity, players > 2, but, as you note, the game board itself has a very high number of potential configurations, so solving the game is presumed to be extremely difficult to impossible. (Possibly [NEXPTIME](https://en.wikipedia.org/wiki/NEXPTIME) if finite and undecidable otherwise.)
  
  The paper [Game strategies for The Settlers of Catan](http://homepages.inf.ed.ac.uk/alex/papers/cig2014_gs.pdf) suggests that the game tree for Catan is not surveyable b/c the options for trade negotiation in natural language aren't bounded:
  
  > One response to this is to develop a symbolic model consisting of heuristic strategies for playing the game. Developing
  > such models potentially has two advantages. First, a symbolic
  > model can in principle lead to an interpretable model of human
  > expert play ... Second, a symbolic model can provide
  > a prior distribution over which next move is likely to be
  > optimal...
  
  The paper mentions this second part to relation to machine learning, where "the posterior distribution over optimal actions acquired through training improves on the baseline prior distribution."
  
  Especially where the game is unsolved and intractable, machine learning has demonstrated strong utility for an increasing number of games, so it is unlikely not to be an optimal component for truly strong play. However, such a system can be a combination of ML and [domain specific knowledge](https://en.wikipedia.org/wiki/Domain_knowledge), such as in [informed search](https://en.wikipedia.org/wiki/Search_algorithm#For_virtual_search_spaces).
  
  The [Optimizing UCT for Settlers of Catan](https://pdfs.semanticscholar.org/0ef6/7eac64e0d7ee2d68abf3976751940616aab9.pdf) goes into this in detail, and also provides reference to prior work.
  
  If your primary requirement is strong utility, some form of machine learning is likely optimal. But it can be fun to attempt to solve games and cobble together sets of heuristics.
  
  > **Comments:**
  > **username_2**: Nice answer. I'm not sure about the claim of NEXPTIME though. I can easily see how it is in NP, but apart from the Natural Language component, it's not clear to me that we can be sure about the hardness of the game.  
  > **username_4**: @username_2 Yeah, I was just making a guess based on [Constraint Logic](https://erikdemaine.org/papers/CL_Complexity2008/paper.pdf) for an imperfect information team game (here "team" b/c player >2, which can result in coalitions.)  I suspect proving it would be daunting indeed, and it doesn't even show up on this wiki chart of [hardness of popular games](https://en.wikipedia.org/wiki/Game_complexity#Complexities_of_some_well-known_games)!  
  
  ---
  
  ### Answer by username_5 on 2019-10-26. Score: 0
  
  From the way you have phrased your question one can derive a couple of strong assumptions which simplify the problem tremendously and make it feasable:
  
  1. We do not look for an agent being able to play the game but only an evaluation of settlement options (no other agents to be considered)
  2. The evaluation of settlement options is static (i.e. does not change over time) and is independent of other settlements
  
  From that two simple ideas come to my mind:
  
  **1. the ML approach**
  Look at historical game data and see which settlement options led to a win. So basically look at tuples of (X,y) with X being something like (W8, C2, O6) meaning that the settlement give access to wood with an 8, clay with a 2 and ore with a 6. And y indicating a win or loss.
  To make it a bit dynamic you could differentiate between initial settlements (being placed at the beginning) and the ones during the game. So for each of these two categories you would derive basically a score for the possible settlements.
  
  If you can compute all the possible combinations you will not even need ML since you can simply run the math once and then look it up. Might be doable in this case as the assumptions mentioned above simplify the problem a lot (compared to fully "solving" the game). Thinking through the possible combinations for a given settlement location (selecting 3 fields with A possible resources and B possible numbers) will quickly give you an idea about that.
  
  **2. The classy symbolic approach**
  What comes to my mind right away is linear programming as it offers a convenient way to model the strategic aspects you have mentioned. You could develop a target function to maximize using scores for different resources and numbers (e.g. you could give clay higher importance than wool). Besides that constraints can capture additional aspects of game strategies like "always make sure to have access to clay" or "do not settle where the 3 resources are the same" etc.
  
  My very first idea to model this is using decision variables like X\_(i,j) with X being 0 or 1, i representing the resources out of {clay, wood, ..., desert} (side note: do not forget the water and different ports here) and j modelling the numbers out of {2,...12}. The constraints would need to model the fact that you need to select 3 of those X\_(i,j) for every settlement.
  
  If you want to calculate this for a given game you would need to feed the model the possible settlement options based on the layout of that specific game. Then run the optimization and it gives you the best settlement option (i.e. the 3 feasable X\_(i,j) maximizing your goal function).
  
  Qua definition you need to bring in game knowledge for this approach. And probably talking to someone who is really good at the game would help to understand what matters.
  
  
  ---
  
  