2
\$\begingroup\$

Is it possible to calculate the best possible placements for settlements in 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?

Edit: Catan is fairly complex, but involves a setup of placing hexagonal "tiles" randomly to make the board (example board below) . One can then, in turn with the other players, place 2 settlements on the board at corners. Settlements cannot be placed on corners directly next to each other, giving you the ability to deny spots to others. Settlements give you the ability to get the 3 resources around them. One needs certain resources to do certain things, but generally even-ish balance of resources through the game. You also want resources with number chips closer to 7, as you only get the resource if the 2 die rolled every turn land on that number. After the 2 initial settlements, you can build roads out and build new settlements. If you have a settlement on a port, you can also trade according to that port's trade type.

see this video for a tutorial on Catan

Catan Board Example

\$\endgroup\$
  • 2
    \$\begingroup\$ Please explain in your post how Catan works. Most of us will probably have never played it before or (as in my case) they don't remember much from it, especially given how I can count three completely distinct catan games just from the top of my head \$\endgroup\$ – Bálint Oct 23 '19 at 7:27
  • 1
    \$\begingroup\$ Catan's quite complex in it's rules and intricacy, but I posted a basic explanation above. \$\endgroup\$ – acj11507 Oct 23 '19 at 7:40
  • 1
    \$\begingroup\$ Keep in mind that this is a site for folks who make games, not folks who prove therems of optimal strategies in games, so we might not be the right experts to help you with this. When we're thinking about strategies, we're generally much looser/more informal than true mathematical optima, using things like empirical observations of human player behaviour (which may be very sub-optimal, but is the experience most of our players will have), or making AI that's deliberately non-optimal but just offers the illusion of intelligence and intent to make it fun to play against. \$\endgroup\$ – DMGregory Oct 23 '19 at 12:34
  • \$\begingroup\$ I'm voting to close this question as off-topic because it's like asking "what's the best algo for playing chess?" It's a huge topic without a canonical answer. \$\endgroup\$ – Almo Oct 23 '19 at 14:21
  • \$\begingroup\$ My bad. It's my first time posting on stackoverflow and I was directed here from the main site. \$\endgroup\$ – acj11507 Oct 23 '19 at 18:39
1
\$\begingroup\$

There are a small fixed set of possible locations on the board so measuring each one against your metrics and picking the best one would be no problem. The issue is, whether you can come up with good, (or merely good enough,) metrics.

In other words, if you want the best place(s) to place a settlement then you need to define what best means. Then the rest is merely calculation.

Without a definition of what best means you would have no way of checking whether a ML algorithm is doing the right thing or not. ML models are currently very hard to understand the workings of. If you train a model and it gives you an answer that seems off, then what do you do?

If you go with a rules-based approach, then if you find the answer is different than you expect you can at least look at the rules and the particular input and figure out which rule caused that answer to be chosen. Then you can tweak the rules as necessary, iteratively approaching best, at least in your judgment.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ To add to this answer: Better yet, you can not only tweak the rules, you can tweak when to choose what rule. Like a bias the bot may have. Does he prefer being futher away on existing cities over a trading harbour? Maybe dont place a city adjacent to an existing enemy road. Maybe the bot may prefer a second city with more duplicate resources around, if he already has a connection to a harbour etc. Just like in Civ Gandi dislikes to go to war... until nuking time! \$\endgroup\$ – PSquall Oct 24 '19 at 11:48
0
\$\begingroup\$

TL;DR

If you use expected values you would not need to use chances explicitly although you would calculate a risk neutral entity.


Your could as you mentioned go for a ML approach here, but you might as well assign each adjacent field its expected value if rolling a set of dice, i.e. its chance [since you get 1 per roll] and maximize over the sum of chances.

If you now want to account for different resources you would factor in your current chance of getting said resource on any roll

I am already adjacent to a forest with a 2, resulting in a 1/36 value, therefore another forest will be less good as if it was my first on, but it would still be very beneficiary for me.

I would guess reducing any new fields value by the summed up value of all accounts of access you have to the given resource already.

Any new forest would have its value reduced by 1/36 in the above example.

But you can go further by factoring in the increased amount of wood and clay needed in the early game and the increased amount of ore needed in late game by additionaly factoring in the amount of points or settlements you already have.

Now you still would want to give the harbours some value in your calculations unless your algorithm/AI cannot yet interchange resources.

Maybe open another question for that part.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ How would you then calculate weight for blocking off others settlements? \$\endgroup\$ – acj11507 Oct 23 '19 at 18:42
  • \$\begingroup\$ well you open a whole new can of worms here, since you first need to evaluate what "blocking off" means in terms of your logic. and so on. In the end if you want to have a perfect algorith ML algorithms would be the better way to go... \$\endgroup\$ – Chund Oct 25 '19 at 6:09

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.