Author Topic: Combinatorics and Graph Theory applied to Carcassonne (Read 14878 times)

evmillan · « **on:** December 11, 2013, 01:04:12 PM »

I want to share with the forum this article (paper) that formalizes some mathemathical aspects of Carcassonne.
Was written by Lucie Kárná in a Conference Applications of Mathematics 2012 at CTU - Faculty of Transportation Sciences, Prague, Czech Republic:

http://www.math.cas.cz/~am2012/proceedings/contributions/karna.pdf

In the References of the paper CarcC is mentioned, Ref. 3

Linkback: https://www.carcassonnecentral.com/community/index.php?topic=542.0

evmillan · « **Reply #1 on:** December 11, 2013, 01:24:45 PM »

This is other paper that analyzes some rules modification called The Magistrates for the Carcassonne to increase strategic gameplay in a computer MOD.
Was written by McGuire like a reading for a class of Creating Games: Mechanics, Content, and Technology at Williams College:

http://graphics.cs.williams.edu/courses/cs107/f07/reading/Magistrates.pdf

evmillan · « **Reply #2 on:** December 11, 2013, 01:30:10 PM »

Implementing a Computer Player for Carcassonne, Master Thesis by Cathleen Heyden, requirement for the degree of Master of Science of Artificial Intelligence at the Department of Knowledge Engineering of the Maastricht University:

http://www.personeel.unimaas.nl/uiterwijk/Theses/MSc/Heyden_thesis.pdf

kettlefish · « **Reply #3 on:** December 11, 2013, 01:46:35 PM »

Nice found

This game makes the people crazy...

Carcking · « **Reply #4 on:** December 11, 2013, 07:14:12 PM »

Nice post evmillan - thanks for sharing!

obervet · « **Reply #5 on:** December 13, 2013, 08:55:23 AM »

If I could go back and do everything again, I would totally figure out a way to do my graduate work on board games.

Paul · « **Reply #6 on:** December 14, 2013, 03:48:05 AM »

Is there an aspect not influenced by Carcassonne games? Fascinating isn't it.

A City, a Road and a Farm walks into a bar...

evmillan · « **Reply #7 on:** December 19, 2013, 07:45:57 PM »

This is other link to "The math behind Carcassonne tiles"

http://www.enworld.org/forum/showthread.php?216994-The-math-behind-Carcassonne-tiles

evmillan · « **Reply #8 on:** December 19, 2013, 08:04:50 PM »

Largest Possible City in Carcassonne? and more about Carcassonne and Graph Theory

http://mathlaoshi.com/tags/carcassonne/

Big Guy · « **Reply #9 on:** December 20, 2013, 05:42:43 AM »

This is an excellent topic. And these papers are fascinating. I've started referencing the possible number of tile side combinations in the reviews I've started, so its very useful to note the 24 combinations that are possible in the base game.

Now I just need to do the math to figure out how many combinations are possible with added tile side types. I've done rough estimates, but they could we WAY off:

Combinations on a 4-sided-tile given 3 tile side types: 24 (3 to the power of 4, or 81 total combinations, discarding the redundancies due to free rotation of tiles)

Combinations on a 4-sided-tile given 4 tile side types: (4 to the power of 4, or 256 total combinations, discarding the redundancies due to free rotation of tiles)

Combinations on a 4-sided-tile given 5 tile side types: (5 to the power of 4, or 625 total combinations, discarding the redundancies due to free rotation of tiles)

Combinations on a 4-sided-tile given 4 tile side types: (6 to the power of 4, or 1296 total combinations, discarding the redundancies due to free rotation of tiles)

kettlefish · « **Reply #10 on:** December 20, 2013, 06:06:31 AM »

Some time ago HiG asked at their twitter page:

How many scoring tiles are placed on that pallet?

Here comes the link to HiG twitter:
https://twitter.com/HiG_Verlag/status/388561189518999552

evmillan · « **Reply #11 on:** December 23, 2013, 08:45:08 AM »

Emulation of Carcassonne using MATLAB

http://www.mathworks.com/matlabcentral/fileexchange/34723-carcassonne

Artificial_Intelligence · « **Reply #12 on:** January 03, 2014, 08:23:22 AM »

Thanks for these articles.

Carcassonne is a very interesting problem from an Artificial Intelligence perpective. Sure enough, tactics is a piece of cake for the computer. Finding the best short-term move is very simple. But finding the right strategical move is another thing, especially if you want the computer to play well with more than 2 players.

In case this is of interest to anyone reading this, I heard that they are making good progress in 2-player limit Poker and are slowly gaining ground in related forms (2-player no-limit and multiplayer limit). Multi-player no limit will come some day...

evmillan · « **Reply #13 on:** January 03, 2014, 12:16:24 PM »

Welcome Artificial_Intelligence to CarcC Forum! The best Carcassonne Forum!

I agree totally with you. Is really hard to beat the iOS App AI in a 2-player game, but in a Multi-player game you can take advantage of some dispute between other players and win often.

Meepledrone · « **Reply #14 on:** June 14, 2019, 04:19:57 PM »

Although this thread has been inactive for quite a long time, I would like to answer Big Guy's question as I made some digging into this very same question while exploring the amount of tiles needed for fan expansions that would add new side types. So here we go...

Quote from: Big Guy on December 20, 2013, 05:42:43 AM

This is an excellent topic. And these papers are fascinating. I've started referencing the possible number of tile side combinations in the reviews I've started, so its very useful to note the 24 combinations that are possible in the base game.

Now I just need to do the math to figure out how many combinations are possible with added tile side types. I've done rough estimates, but they could we WAY off:

Combinations on a 4-sided-tile given 3 tile side types: 24 (3 to the power of 4, or 81 total combinations, discarding the redundancies due to free rotation of tiles)

Combinations on a 4-sided-tile given 4 tile side types: (4 to the power of 4, or 256 total combinations, discarding the redundancies due to free rotation of tiles)

Combinations on a 4-sided-tile given 5 tile side types: (5 to the power of 4, or 625 total combinations, discarding the redundancies due to free rotation of tiles)

Combinations on a 4-sided-tile given 4 tile side types: (6 to the power of 4, or 1296 total combinations, discarding the redundancies due to free rotation of tiles)

In order to answer Big Guy's open questions, we can generalize the application of the Burnside's Theorem discussed in the following thread:

Quote from: evmillan on December 19, 2013, 07:45:57 PM

This is other link to "The math behind Carcassonne tiles"

http://www.enworld.org/forum/showthread.php?216994-The-math-behind-Carcassonne-tiles

This is the quick answer to Big Guy's questions:

Let C(N) be the number of tile side combinations with N side types.

C(N) = ( N^4 + N^2 + 2 * N ) / 4 = N * ( N^3 + N + 2 ) / 4

So, when varying N, you have the following cases:

C(1) = 1
C(2) = 6
C(3) = 24 (case for Carcassonne standard side types: city, road and field)
C(4) = 70
C(5) = 165
C(6) = 336
C(7) = 616
C(8) = 1044
C(9) = 1665
C(10) = 2530

And so on...

This means that if river sides, for example, were added to the game as a regular side type in addition to city, road and field side types, instead of the 24 tile types, you would have 70 tile types according to its sides. That means 70 - 24 = 46 additional tile types to the current tile types if you would like to be able to fill any gap possible.

Keep in mind that, on top of these figures, you may consider to create additional variations affecting the internal layout of the structures on a tile: city splitters or joiners, field splitters or joiners, monasteries, road connections and junctions, you name it.

As a side note, all this explains why expansions introducing forest or mountain sides require so many tiles even when you try to keep the number low (sorry Wolnic!)... Now you can see how many tiles you would need to create expansions with new side types.

The other option would be to establish some placement rules that limit the number of combinations during the game, such as the placement rules of the river tiles at the beginning of the game.