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

Offline evmillan

  • Duke
  • *
  • Posts: 164
  • Merit: 3
    • View Profile
Combinatorics and Graph Theory applied to Carcassonne
« 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: http://www.carcassonnecentral.com/community/index.php?topic=542.0

Offline evmillan

  • Duke
  • *
  • Posts: 164
  • Merit: 3
    • View Profile
Re: Combinatorics and Graph Theory applied to Carcassonne
« 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
« Last Edit: December 11, 2013, 01:30:29 PM by evmillan »

Offline evmillan

  • Duke
  • *
  • Posts: 164
  • Merit: 3
    • View Profile
Re: Combinatorics and Graph Theory applied to Carcassonne
« 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

Offline kettlefish

  • Global Moderator
  • Chatelain Chevalier
  • *
  • Posts: 4565
  • Merit: 123
    • View Profile
Re: Combinatorics and Graph Theory applied to Carcassonne
« Reply #3 on: December 11, 2013, 01:46:35 PM »
Nice found  :(y)

This game makes the people crazy...

Offline Carcking

  • Global Moderator
  • Duke Chevalier
  • *
  • *
  • Posts: 1853
  • Merit: 31
  • I call Red!
    • View Profile
Re: Combinatorics and Graph Theory applied to Carcassonne
« Reply #4 on: December 11, 2013, 07:14:12 PM »
Nice post evmillan - thanks for sharing!
I just drew the perfect tile for my MonKnighThieFarmer!

Offline obervet

  • Authors
  • Count
  • *
  • Posts: 362
  • Merit: 36
    • View Profile
Re: Combinatorics and Graph Theory applied to Carcassonne
« 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.  ^-^

Offline Paul

  • Marquis Chevalier
  • ***
  • Posts: 2453
  • Merit: 86
    • View Profile
    • sydby.com
Re: Combinatorics and Graph Theory applied to Carcassonne
« Reply #6 on: December 14, 2013, 03:48:05 AM »
Is there an aspect not influenced by Carcassonne games? Fascinating isn't it.  :meeple:

A City, a Road and a Farm walks into a bar...
World record holder for a single game of Carcassonne using 10 007 tiles!

Offline evmillan

  • Duke
  • *
  • Posts: 164
  • Merit: 3
    • View Profile
Re: Combinatorics and Graph Theory applied to Carcassonne
« 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

Offline evmillan

  • Duke
  • *
  • Posts: 164
  • Merit: 3
    • View Profile
Re: Combinatorics and Graph Theory applied to Carcassonne
« 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/

Offline Big Guy

  • Authors
  • Duke
  • *
  • Posts: 223
  • Merit: 11
  • I slipped away, like a THIEF in the KNIGHT
    • View Profile
Re: Combinatorics and Graph Theory applied to Carcassonne
« 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)
A good board game brings people together.

Check out my Variants:
THE TOWER (NCV)
PLAY AS THE DRAGON

Offline kettlefish

  • Global Moderator
  • Chatelain Chevalier
  • *
  • Posts: 4565
  • Merit: 123
    • View Profile
Re: Combinatorics and Graph Theory applied to Carcassonne
« 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

Offline evmillan

  • Duke
  • *
  • Posts: 164
  • Merit: 3
    • View Profile
Re: Combinatorics and Graph Theory applied to Carcassonne
« Reply #11 on: December 23, 2013, 08:45:08 AM »

Offline Artificial_Intelligence

  • Vagabond
  • *
  • Posts: 3
  • Merit: 0
  • Carcassonne lover - one of the best game design!
    • View Profile
    • Happy Meeple
Re: Combinatorics and Graph Theory applied to Carcassonne
« 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...



Play board games online on www.happymeeple.com/en/
Cards and dice games: Lost Cities, Finito, Level X, KeltisCard, Keltis

Offline evmillan

  • Duke
  • *
  • Posts: 164
  • Merit: 3
    • View Profile
Re: Combinatorics and Graph Theory applied to Carcassonne
« 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.

Online Meepledrone

  • Global Moderator
  • Viscount
  • *
  • Posts: 791
  • Merit: 89
  • It is full of... Meeples!!!
    • View Profile
Re: Combinatorics and Graph Theory applied to Carcassonne
« 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...

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:

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.


Share via delicious Share via digg Share via facebook Share via furl Share via linkedin Share via myspace Share via reddit Share via stumble Share via technorati Share via twitter

  Subject / Started by Replies / Views Last post
xx
Carcassonne & Co. Newsletter - announcing a new "Spiel '14" Carcassonne tile

Started by wamboyil

60 Replies
24050 Views
Last post January 20, 2015, 04:39:08 PM
by eddebaby
xx
CAR for Carcassonne v2

Started by totor66

61 Replies
13606 Views
Last post May 12, 2017, 11:26:29 AM
by Vasek
xx
My First Carcassonne

Started by flipshot

0 Replies
946 Views
Last post August 24, 2017, 12:32:53 PM
by flipshot
xx
Carcassonne for Mac

Started by Jéré

20 Replies
7684 Views
Last post October 15, 2015, 01:55:32 AM
by sheeple
xx
Anyone using the OSx Carcassonne?

Started by Maash

0 Replies
711 Views
Last post January 26, 2018, 11:54:29 AM
by Maash