20

Let's start this question with the following assumptions about a game of Carcassonne:

  • It's a two player game.
  • The game is using the current basic set of rules/tiles. edit: just to be clear, I'm using 3rd edition rules that score all city tiles the same 2 points and count the same city for different farms as described here.
  • The player we want to maximize has perfect luck and perfect competence both drawing the tiles and placing them.
  • The opponent has minimum luck and competence.

This means we can choose what tiles are drawn by each player, how they are played and how to place each players' meeples.

Is there an optimal way of placing the tiles in order to maximize one player's score? If so, can that way be determined?

6
  • I don't remember the quantity of each pieces, but we can calculate it without building a map, assuming that we can build the most of points like there were only 1 player. So probably an excel would solve most of the case.
    – gbianchi
    May 15, 2012 at 13:14
  • @user1873 Meeple placement is indeed optional. We can definitely assume the opponent never places one. I never heard of different scoring systems, although I assumed there are older and newer versions of the rules. Going to look that up as soon as I can.
    – rahzark
    May 15, 2012 at 13:31
  • 1
    If the opponent has minimum luck and competence, can we also then assume they 'accidentally' always place tiles in positions that give the first player more possibility for points, or indeed finish the first player's features for them? That would effectively be like a 1 player game where you can only place a meeple every other go.
    – Nick Shaw
    May 15, 2012 at 20:18
  • @user1873 isn't that a rule on one of the expansions? I couldn't remember which one, but I think that when you play it on brettspielwelt it use that rule.
    – gbianchi
    May 17, 2012 at 14:15
  • 1
    this question solve your point problems boardgames.stackexchange.com/questions/7/…
    – gbianchi
    May 17, 2012 at 17:32

7 Answers 7

13

Note: This answer below is using 1st Edition scoring rules (Cities only scored once). Although parts of the analysis are valuable to calculating the highest score possible (36 Scoring opportunities, try to score with Meeples that have a high point value per the 36 turns, the highest score of 278 is not correct. I will have to do further analysis to determine if 7 farms can be created scoring the most cities multiple times, will result in a maximal score. (Edit: The maximum theoretical score is 338, as posted in my other 3rd Edition rules analysis)

Hackworth's analysis about optimal play exists is correct, although he is right about the difficulty in evaluating all possible moves, I believe that tengfred is closer in estimation of what we need to determine the maximum score possible. We only need to evaluate ending maps, not all possible moves from the beginning to the end. Once we have found the maximum scoring map, we only need to backtrack to find a legal set of moves that will lead to that end map. That is as tengfred points out, a much smaller problem.

The Rules show 72 tiles, and scoring as follows:

Road (1 point per tile), Cities (2 points per tile, 2 Points per pennant), Cloister (1 point for each tile, cloister tile and surrounding tiles), Farm (3 points per completed city)

A similar question was asked on The Opinionated Gamer.

My challenge to you is to see how many points you can score using only the 72 tiles in the base set – following all of the rules as printed in the box — EXCEPT that you can only use one meeple!

Wie Hwa (animation) solved that problem with 277 points. Wie Hwa's end map

He didn't always score on odd turns, so his solution isn't the correct answer to this question. But, someone with more desire than me might want to take his end map and modify the order of the turns so that player 1 is always the one to score.

This gets you a grand total of 278 points (the board actually will have an unmatched city tile that cannot score I think, and still place a farmer). It is amazing that Wei Hwa almost achieved this using only a single meeple in single player. Feel free to figure out if his end map is an optimal solution for 2-player.

The maximum number of scoring opportunities is 36 if you go first since you can only place meeples on your turn. The optimal solution will include:

  • one farmer, 45 points
  • 15 completed cities, 116 points (10 pennants = 20 pts, 48 city edges = 96)
  • 6 cloisters, 54 points.
  • The remaining points divided between the most points that can be scored on roads with the remaining 14 moves (1x Quad road = 4 pts,7x Tri Road = 21 points, 32 straight/elbow non terminals, 5x Dead End)
8
  • Wonderful answer, totally worth looking into! By the way, the question was never changed :p
    – rahzark
    May 17, 2012 at 13:38
  • Hmm, with the above graphic, you can have many more than 1 farm - the one massive central one, yes, but also potentially 6 other farmers on closed 'edge' pieces of fields around the perimeter - such as at the bottom - all those tiles with mostly city but a small bit of field underneath are all separate "farms", and thus you could score that big city 7 times (using all 7 scoring-meeple as farmers by game end) = 21 points for farmers for just that city. Add the farmer score for the remaining 14 cities for the massive farm gets you to 63 points for farming. Any advances on that for the farms?
    – Nick Shaw
    May 17, 2012 at 21:07
  • @user1873 Those are the old Carcassonne rules. In newer versions of the ruleset, you do very much score per farm controlled, not per city farmed. May 18, 2012 at 7:08
  • Ah yes, old farm scoring is quite different to newer farm scoring (which is MUCH simpler). Perhaps @rahzark needs to confirm in the question whether he means old or new rules scoring (as also old scoring also has 2-tile cities only scoring 2 points, whereas new scoring makes all city tiles worth 2 points each, so a 2-tile city is 4 points).
    – Nick Shaw
    May 18, 2012 at 7:51
  • @NickShaw People, read the question!! I have written: "The game is using the current basic set of rules/tiles." It even links to the rules I'm talking about! Either way, I'm going to edit it now.
    – rahzark
    May 18, 2012 at 8:20
9

As Hackworth notes, testing all possible layouts is obviously infeasible. However, it might be possible to get a decent upper bound on the points.

I think we can safely assume that meeples will not be a scarce resource when playing in this way (since we can choose to complete the map in any order, it should not be difficult to ensure we always have meeples available). Thus the problem is reduced to finding the highest scoring map-layout. The upper bounds for roads, cities and cloisters are easy; 9 for each cloister, 2 for each city tile (and 2 for each pennant) and 1 for each road-tile.

The farms are the tricky part. First we would have to figure out the maximum number of cities we can make, and second, we need to figure out the maximum number of farms that can supply each city, with the limit of max 7 fields total. This is certainly not easy, but should be a lot easier than the original problem (there are a limited number of ways in which a city could be supplied by multiple farms, etc).

You could probably get a decent approximation by just playing around with the tiles for a few hours...

3
  • I very much concur with this answer, and was in the process of trying to ascertain the potential max farm score in such a scenario before @tengfred got in there first with this answer (nice one, tengfred). I'm not sure I agree with the "max 9 fields" though: We only have 7 meeple to score with, so that would mean a max of 7 distinct farms from which to score from. And only shared cities (cities that adjoin two farms, bordered by road or playing-area-edge) would give extra scoring, and there's a limit to how many cities can adjoin multiple farms, so it should be calculable...
    – Nick Shaw
    May 17, 2012 at 9:56
  • Yes, that's what I meant by 7 "scoring" farms. You can score a single city more than once if the city in question borders 2 separate fields - that's where the complexity lies; positioning cities near the edge of play such that you can use the small field areas on the very edge of play as separate farms for scoring.
    – Nick Shaw
    May 17, 2012 at 21:01
  • Yes, it should be 7 farms, for some reason I got the idea you had 9 meeples. Edited the answer.
    – tengfred
    May 21, 2012 at 6:58
8

342

For third edition rules

Here's one way how: setup after all moves The numbers show when tiles are placed. Black is the first player to move and always places a meeple where the number is. Blue moves second and never places a meeple.

Proof of optimality

Meeple usage optimality:

The first player to move will have 36 turns and thus only 36 opportunities to place meeples for points. The best usage of those 36 is:

  • 7 for fields
  • 6 for cloisters
  • 16 for cities
  • 7 for roads

No more can be placed on fields since you don't get those back. The number on cities and cloisters are sufficient to count all possible city/cloister points (except the odd city tile, see city optimality). So the only possible useful change would be to get more roads, which adds at most 2 because all roads without endpoints are already scored. But 2 is less than the amount we would lose by having less cities (each extra city adds 3 field points to each big field), cloisters (9 each), or small field (6 each).

City optimality:

There are 44 city tiles and 10 shields. 5 of the city tiles have two separate cities on them and so if you put them on separate cities they can be counted twice. This would all be worth 59 points and completed cities are worth double making 118. However all completed cities must have an even vertical perimeter and an even horizontal perimeter because they must be complete on both left/right and up/down (a diagonal city tile has 1 horizontal and 1 vertical perimeter, not 1 total perimeter). For example say a city is 5 tiles tall, then its vertical perimeter must be 10 if completed, yes you could have concavity but the same rules apply to that. And since the total horizontal+vertical perimeter of all available tiles is odd, you cannot complete all city tiles, the best you can do is leave out one tile. This means the maximum city score is (59-1)*2=116.

Field optimality:

We need to maximize the number of completed cities since we can construct big fields that touch all cities. A completed city must have at least 4 tiles with a corner that do not have their own city touching them. Diagonal city tiles (i.e black #29) have 1 such corner and the simple side piece cities (i.e. the starting tile) have 2 such corners (all other city tiles have 0). There are 10 diagonals city tiles and 28 simple side piece cities (tiles with 2 simple side piece cities count as 2). This gives 10+28*2=66 corners which allows for a maximum of 16 cities.

Now to maximize the number of fields that touch these 16 cities. I will attempt to explain this intuitively but user1873 came to the same conclusion and proves it using graph theory (see their answer - which is the same in other ways except only has 15 cities). At most we can have 2 big fields touching all cities. A third field must be stuck inside these big fields and therefore only touching only 2 cities. In order to touch a third city it would have to cross one of the big fields, but this would split that big field into two smaller fields.

So we have 2 big fields touching 16 cities and 5 small fields touching 2 cities. 2*16*3+5*2*3=126

Road optimality:

Each completed road has 2 end points. There are 32 road tiles without end points which can fit into any completed road. So the maximum points you can get from roads are 2 * #roads + 32. Since we only have time to place meeples on 7 roads this gives 2*7+32=46.

Cloister optimality:

Each of 6 cloisters can score a maximum of 9 for 6*9=54.

Sum of optimal features 116+126+46+54 = 342

I have to say that this is a beautiful question because not only is the proof multi faceted with outside the box thinking required, but because actually finding a configuration that achieved it was really nontrivial and fun. So much so that even 6 years later I remember the joy of figuring out to put that gap in the city to allow it to complete and the tile missing to prevent the two big fields from joining. That beauty is why I've revisited this and rewritten this answer to make it more clear and also to break it down into an example with all moves and a separate proof.

An open question would be what the maximum possible score in a one player game is. You'd have 31 more turns to place meeples but the only possible points to grab would be completing more roads. There are 12 road endpoints unused in my example but how in the world would you rearrange them to connect with each other without breaking other things? Another open question is what the total collaborative score is for games of 2-5 players. This would be tricky since sharing cities, fields and even roads would need to be done as much as possible but it surely won't be possible to share everything. These questions will be an order of magnitude harder to solve and prove optimal.

3
  • "I don't think it is actually possible to close all roads while still achieving that many fields), this could at most net 12 more points." I know my theoretical score didn't correctly count that 16 cites can be closed with the city tiles, but you might want to correct the statement above. You can only score 1 point per road, and there are only 46 tiles with roads on them. You couldn't net an additional 12 points. I agree these theoretical scores are maximums, that is why I also included average points per meeple. For example in your configuration above there are 3 roads that cannot be scored
    – user1873
    Oct 8, 2014 at 3:22
  • Still, 339 is an impressive score, near enough to the maximum that it would be valuable to expand this answer to include all the moves for the 1st/2nd player that make that player score 339. It should be pretty trivial to work out that answer.
    – user1873
    Oct 8, 2014 at 3:26
  • You can use the Contact Us form to have your accounts merged so that you can freely edit your answer
    – Glorfindel
    Jan 13, 2021 at 9:50
8

Is there an optimal way of placing the tiles in order to maximize one player's score?

Yes

With a finite amount of tiles, a finite number of legal placements for any tile at any point in the game, and a finite amount of meeple plays after placing a tile, it should be obvious that there are a finite number of possible games. Every game has a definite result in terms of score, so clearly, there must be at least one game that produces the highest possible score.

If so, can that way be determined?

Yes

Obviously, in theory you could just run all possible plays through a computer and find the best.

In practice, my gut feeling as a programmer tells me that an exhaustive search through all plays would, on current hardware, quickly become useless due to a combinatorial explosion, simply because the search tree becomes too broad to handle incredibly fast.

Just for a rough idea, a sample calculation:

The base set has 72 tiles. After placing the starting tile, you have 71 at your disposal.

  • The starter tile is designed to allow every single of those 71 tiles to be placed in 1-6 distinct ways, not counting irrelevant, merely graphical rotations.

  • Assuming a mean of 3 ways per tile, for the first move alone, you have roughly 200 possible maps after the 2nd tile has been placed.

  • Next turn, you have only 1 fewer tiles, but far more possible ways to place the average tile, because the number of single edges has increased by 2, or increased by 50% in this case. You are probably looking at around 300 possible moves now.

  • Even if the sum of possible tile placements for all remaining tiles stagnate at 200 per move on average (which is probably way too low an estimate), after 10+1 moves of 71+1, you already have 200^10 = 10^23 different maps.

  • Calculating 10^12 maps per second (probably out of reach for typical desktop hardware), it would take over 3000 years just to calculate all possible maps after 11 moves.. Make that a million Desktop PCs, and you're looking at a full day to calculate the first 11 moves. Next move, multiply by 200, and so on.

  • And all that is assuming nobody places any meeple during those turns, which again vastly increases the search space!

  • In conclusion, I find it highly unlikely that anyone has ever calculated anything close to an exhaustive set of possible Carcassonne maps, let alone the definite high score anyone can theoretically achieve.

I understand that neither of these answers is particularly helpful, but I believe that's pretty much all you can say about the problem without writing a scientific paper.

8
  • I agree with what you said. What about non-exhaustive searches? Is there a placement algorithm that can maximize this problem?
    – rahzark
    May 15, 2012 at 13:36
  • @rahzark I bet you could try something with neural nets or genetic algorithms to let the AI figure out which moves are generally the most lucrative in the long run, assuming no opponent interference and free choice of all tiles. However, the problem remains that the search space is so vast, and any sort of "learning" algorithm can only sample a vanishingly small portion of that space. You could always land in a local maximum and believe you have found a pretty good solution, while missing the mountain right next to it.
    – Hackworth
    May 15, 2012 at 14:06
  • Rather than attempting to solve an extremely hard problem, you could just solve a simpler one, and figure out some good upper bounds based on the number of available tiles of each type. You'd overestimate, but it'd be nearly as useful as a theoretical maximum that you'll never achieve either!
    – Cascabel
    May 15, 2012 at 14:48
  • 1
    @rahzark I don't see how meeples make the problem easier. The most trivial counter-example is the first move: Without meeples, you have only 1 move for the first turn. You place the starting tile, and pass. However, if you do place a meeple, you have 4 different game states after the first move, each of which can influence the subsequent meeple moves. It's like another game literally on top of the tile placement game.
    – Hackworth
    May 15, 2012 at 15:39
  • 1
    @rahzark That's the question though, isn't it? Is one big city really optimal, since it only counts as 1 town for your farms? Is it not better to have multiple farms, each adjacent to many small towns? Also for roads: with 3 tiles, you can make 1 road of length 3, or 2 roads of length 2 each. You see, there are many different ways to do things, and without a computer, you will have a hard time deciding which matters most.
    – Hackworth
    May 15, 2012 at 16:02
5

The maximum theoretical score is 338. I previously answered the question for 1st Edition rules (cities only scored once by farmers), so here is my second stab at this question. First, it should be rather clear to everyone that since there are only 72 tiles and one is the starting tile, that the maximum number of scoring opportunities is 36 if you go first. You can only score by placing a meeple on your turn, regardless of whether you our your opponent lay the tile that actually scores that meeple. It should also be clear that the optimal score consists of scoring the highest possible points for each meeple that you can score. Here are the maximum scoring possibilities.


  • 1x Long Road: A long road will score 32 pts. + 2 pts. = 34 pts.
  • 2x Big Farm: A Big Farm will score 3 pts. x 15 cities = 45 pts.
  • 6x Cloister: A Cloister will score 9 pts.
  • 15x Cities: Scoring all 15 cities is worth 2x (10 pts (pennant) + 48 pts (city tiles)) = 116 pts
  • 5x Small Farm: A small farm will score 3 pts. x 2 cities = 6 pts.
  • 7x Short Road: A short road will score 1 pts. x 2 road tiles = 2 pts.
  • Total Score = 34 + 2x45 + 6x9 + 116 + 5x6 + 7x2 = 338 points

Notes regarding average score per Meeple.

A Big Farm requires that you have completed 15 cities. The maximum number of Big Farms is two. Imagine the two farms as either Inside/Outside, Left/Right, Up/Down, etc. In the graph below, the Big Farms would be A and B and there would be 15 nodes in-between them. This can be shown to be true using Euler's Theorm, regarding the K(3,3) Utility Graph problem. Average points ~10.72. This calculation comes from total city points (116) + (90) 2 Big Farms + (30) 5 Small Farms = (236 pts/(15 Knight+7 Farmer=22 Meeples))

K(3,3) impossible planar graph

The maximum number of small farms is 5, since you only have 7 Meeples and 2 will be unavailable as Big Farmers. These small farms will sit like node C, in-between two cities only.

The Long Road requires using all non-terminating road tiles (32), and two road tiles that dead-end into a city/cloister. Constructing a single longest road is not necessary to find a highest scoring map, as long as any non-terminating road tiles are included in the Short Roads you score.

The maximum number of cities is 15 (with one unused edge). Average points ~7.73.

The maximum number of Cloisters is 6. Average points 9.

The maximum number of Short Roads is all Meeples minus those previously used with higher average scores (36 - (1+2+6+15+5)) = 7 Meeples. As noted earlier, these short roads can use non-terminating segments that were not used in the Long Road scoring. The only thing required to obtain the highest score possible is that all 32x non-terminating road tiles are used among the 8x Long/Short Road meeples. Average score for all 8 road meeples 48 / 8 = 6 pts.

12
  • Your statement about the breakdown of the farms by number of cities isn't necessarily correct. Consider a case with four cities and four farms. Using your method the optimum graph would involve two farmers connected to four cities each and two connected to two cities. In fact it's possible to connect each farmer to three cities (think of a cube with cities/farmers at the vertices).
    – tttppp
    May 22, 2012 at 11:24
  • ..which scores exactly the same number of points (sorry - I miscounted!)
    – tttppp
    May 22, 2012 at 11:45
  • @tttppp, I am pretty sure the K(3,3) Utility Graph problem was solved a long time ago and verified by many different mathematicians (Euler, Kuratowski, Thomassen, etc.). I sincerely doubt that those guys who are much smarter than me got this wrong.
    – user1873
    May 22, 2012 at 13:45
  • You didn't exactly prove the reduction from this question to that theory though!
    – tttppp
    May 23, 2012 at 8:15
  • @tttppp, I think that proving that K3,4 is a subgragh of K3,3 and therefore is also nonplanar is beyond the scope of this SE. This is not Math.SE, and I do not believe that such a proof (or explanation of one) is necessary. Is it just the Utility Graph reduction you are worried about, or do you believe that my highest Average points per Meeple reduction to the problem is flawed.
    – user1873
    May 23, 2012 at 13:14
1

285

For first edition (and 272 for 2nd edition which is optimal for that edition as well). This question was for the 3rd edition, but the older editions lead to different and interesting ideas so I thought I'd answer it for that as well.

A game with the most 1st edition theoretical points possible would:

  • Have all roads scored and all end points on separate tiles (you can't count each endpoint on the same tile as its own point if they are on the same road).
  • Have as many completed and scored cities as possible and no small cities (in the 1st/2nd edition completed cities with only 2 tiles are only worth 2 points). And like roads, tiles with multiple cities must end up being in separate cities.
  • Any incomplete city tiles scored.
  • All cloisters complete and scored.
  • All cities scored by at least one field (cities cannot be counted by multiple fields as in the 3rd edition).

On max number of cities while minimizing small cities

For conciseness, let 2C mean a tile with a city on two sides, etc.

So from the 3rd edition answer of 342 we know that 16 cities are possible and how to calculate the number of possible cities. By that calculation (66 corners), we have 5 extra 2Cs (3 inline and 2 diagonal) that can be inserted into a small city without lowering the number of total cities. That leaves us with only 9 small cities. From here we can lower the number of small cities but to do so requires also lowering the number of total cities. Each fewer small city gains 2 points, but each less city loses 4 points (each city in a field is worth 4 points in the first edition). To start we can take 4 more 2C and then we would have 5 small cities and 15 cities, a gain of 4 points. We can't do this again though because then there is no way to complete the city with the 3Cs and 4C with using many 1C pieces inefficiently. But we can take two 3Cs and surround each with three 1Cs. Then we have 2 small cities and 14 cities, an improvement of 2 more points. Finally we can take a single 3C and surround it in the same way, this brings us to 0 small cities, and 13 cities. That doesn't add any more points but is still better because it will take less turns/meeples since each city needs to be scored. There are many city configurations that can achieve this but none can do better.

To summarize our options are:

  • 9 small cities, 16 total cities
  • 5 small cities, 15 total cities (+4)
  • 2 small cities, 14 total cities (+6)
  • 0 small cities, 13 total cities (+6)

How many points would that give?

  • Roads: 30 endpoints and 32 non endpoints, so 62
  • Cities: 44 city tiles, 1 can't be completed, 5 have 2 cities, 10 shields so (44-1+5+10)*2+1 = 117
  • Fields: 13 cities * 4 each = 52 (39 in 2nd edition as fields go down to being worth 3)
  • Cloisters: 6 cloisters * 9 each = 54

Total: 62 + 117 + 52 + 54 = 285 points

How many meeples (turns) would that take?

The fewest number of roads possible is 15 since there are 30 endpoints (it would be more if you had any pure loops). The fewest number of fields that can touch all cities is 1. Therefore we need at least: 15 (roads) + 13 (completed cities) + 1 (incomplete cities) + 1 (fields) + 6 (cloisters) = 36 meeples.

It just so happens that we need exactly as many opportunities to place meeples as there are turns for the first player, that's a crazy coincidence! Which means it is just barely possible to nab all possible features in an optimal solution. This also means it's impossible to score any more points even if playing solitaire.

Is it possible to construct a map that meets all these criteria?

With much guided trial and error I found one possible way to build said map: enter image description here It wouldn't be hard to find an order of laying tiles and placing meeples to achieve this because you won't need to coordinate all 7 meeples being the in the fields like you would for the solution to the third edition. At the end all you need is 1 meeple in the big field and 1 on the incomplete city tile.

This was easier to construct than the 3rd edition solution in terms of fields but much harder in terms of roads.

0

I dont think one needs to know all possible arrangements to calculate the maximum score. There are a finite amount of city tiles for example which, if the cities are closed, give 2 points each (not counting shields for simplicitys sake). So basically, the question on how many points one can get from the cities is to ask if one can build one massive city with the city tiles. Or how many small cities can be made. The points will be the same in both cases

4
  • 1
    The points will not be the same, because many small towns count more for a farm. Also, one town can count for several farms, so that is good for the score as well. So, which number and arrangement of towns makes the optimal number and size of farms? And what about roads, cloisters?
    – Hackworth
    May 16, 2012 at 7:26
  • @Hackworth: "Many small towns count more for a farm" - huh? A town is the same score for a farm regardless of its size (at least in the basic game). But you are right that some towns can count for several farms - but not many; there's a limit to how many farms can share a single town with the base-game's tiles. So really, work out the max number of cities you can make, and the max number of farms that can share the max number of cities, and you have the max score for a farm.
    – Nick Shaw
    May 17, 2012 at 9:59
  • A big city will not score the same as many small cities because several tiles can count to 2 cities (so that tile scores twice in the game), but if both parts of that tile are part of 1 city will only score once. Having said that I think it's a great way of approximating a "highest possible score". Good thinking @Jake! ... I think for it to work the best way is to make as many cities as possible with the tiles, then assume all the cities belong to two farms and all roads belong to the same player, and that that player would be the KING.
    – noelicus
    May 17, 2012 at 11:51
  • Hackworth, yes of course, but I was talking about city points only. In any case, I was not completly right anyway but my point remains valid i think, that is, one does not need to check all possible arrangements to find the maximum score.
    – Jake
    May 21, 2012 at 11:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .