Tell me more ×
Board & Card Games Stack Exchange is a question and answer site for people who like playing board games, designing board games or modifying the rules of existing board games. It's 100% free, no registration required.
up vote 10 down vote favorite
2

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?

share|improve this question
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 '12 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 '12 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 '12 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 '12 at 14:15
1  
this question solve your point problems boardgames.stackexchange.com/questions/7/… – gbianchi May 17 '12 at 17:32
show 1 more comment

5 Answers

up vote 3 down vote accepted

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.

share|improve this answer
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 '12 at 11:24
..which scores exactly the same number of points (sorry - I miscounted!) – tttppp May 22 '12 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 '12 at 13:45
You didn't exactly prove the reduction from this question to that theory though! – tttppp May 23 '12 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 '12 at 13:14
show 7 more comments
up vote 12 down vote

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)
share|improve this answer
Wonderful answer, totally worth looking into! By the way, the question was never changed :p – rahzark May 17 '12 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 '12 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. – thesunneversets May 18 '12 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 '12 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 '12 at 8:20
show 3 more comments
up vote 9 down vote

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...

share|improve this answer
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 '12 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 '12 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 '12 at 6:58
up vote 8 down vote

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.

share|improve this answer
I agree with what you said. What about non-exhaustive searches? Is there a placement algorithm that can maximize this problem? – rahzark May 15 '12 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 '12 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! – Jefromi May 15 '12 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 '12 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 '12 at 16:02
show 3 more comments
up vote 0 down vote

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

share|improve this answer
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 '12 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 '12 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 '12 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 '12 at 11:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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