Since Caylus is a perfect information game with absolutely no random elements, wouldn't it be possible to "solve" 2-player Caylus with a supercomputer? For each possible move of your opponent, it would calculate the tree etc. Or if it's as complex as go... then it's impossible

I think there are to many possibilities to (reasonably) build a tree of them.
First there are the different start setups of the pink buildings and who is start-player. 6 Buildings - 2 Players... means you have already 1440 different Start-Setups in a 2playergame.
As a Comparism: Chess and Go have only 2 Statsetups: I start or opponent start.
Then there'll be the first move.
Your oponent could spend 0-6 people on >10 possible fields.
So lets say 4 people on 10 different fiels for example that means 10*9*8*7=5040 different possibilities

Multiplied with the 1440 different setups you'll be at roughly 7 Mio possibilities after just one turn. Simple Math
Not having regarded yet, that he could have build different buildings and won grants by the king and a different number of buildings could be activated that round.

Sure - there will be much less different outcomes (but with the combination of different buildings in which order on plan, grants taken, winning points, goods stored etc. still a lot) and you COULD eliminate some possibilites because they seem not useful but I think my example shows, that building a tree of possibilities with such a complex game is not really an option.
You'll need to programm some kind of mechanisem to analyse the game situation - an Intelligence...

Termi

In this simplified example, you'll have to go with combinations instead of permutations, i.e., (10*9*8*7)/(4*3*2)=210

Can we have a Game Theory Fan geekbadge? Pretty please?


Anyway, maybe Caylus is solvable (the more i think about it the probable that is). However, who is gonna program this? You cannot go with raw computer power alone without some guidelines, opening theory and such. Have these things been established for Caylus in a universally accepted way?

Unfortunately i don't think IBM (or Microsoft) will be interested enough to put several M$ on this project

720. For purposes of solution it doesn't matter who goes first, only what they do.

However, you're right. The supercomputer that can solve chess doesn't exist, and that only has 400 possible game states after each player has moved once. Even assuming nobody plays to blank spaces or the Gold Mine on turn 1, in Caylus there are 151200 possible game states after each player has placed only a single worker. That's a tree 378 times larger than that of chess, and you haven't even come close to finishing the first turn.

I think you miscalculated. With two players, there can hardly be more than 100 to 200 states (too lazy to haul out the board and calculate exactly) because each player can only chose approximately 10 to 12 different locations on which to place a worker. Admittedly, if you increase the number of players the amount goes up, but the OP mentioned the 2P-game specifically.

There are 6! (720) possibilities in the setup alone, regardless of where people play. Then there are 15 places for the first person to play (6 pre-bridge, 8 after, and pass) and 14 for the second. Total: 151200. That is not considering the difference between the values of playing for the second person if the first person passed.

The different number of turns taken by each player and the change in values of placing workers after the other player passed would make this a much more challenging problem.

So you're too lazy to be bothered working it out or even counting the potential playing locations, but you still think you can turn around and criticise my numbers. Right. Your opinion has been noted and will be treated with the respect it deserves.

As it happens, I did miscalculate slightly - I forgot that there are two moves which can be made by any number of players. If the first player passes or plays in the castle, the second player has 15 options to choose from instead of 14. Adjusting, the actual number of possible game states after setup and first placements is 152680.

Not impossible!

In fact, let's challenge some computer geek to build a distributed computing solution. We can all run "the Caylus project" and given enough of us, we'll solve this thing in no time

Yesss!!!

Know any good computer/math geeks?

Something else we should work on, if it doesn't already exist, is a standard notation system to log games.

Any 2pl game with no luck is theoretically solvable; it's just a question of time. Thus, games like Chess, Go, and Caylus are all solvable ... but unlikely to be 'solved' any time soon.

By comparison, Tic-Tac-Toe is certainly solved, as is Connect Four.

What really intrigues me here is the idea of player 1 passing as their first action. Has anyone actually tried this in a game?

No, but it shouldn't have much of an impact. The first player should gain +1 coin over the second player (in cube-equivalence, where a cube is worth 3 coin).

However, depending on the starting arrangement, the cloth might be worth hitting at a cost of 3 coins for the second player. And then hitting it again in turn two when he goes first.

Sorry, no :-( They're all terrible :-p

I was never THAT good at probabilities, but I'm pretty sure I was right here.

If you place the first worker, you got 10 possibilities - 10 different cases.
Then your opponent places one on one of the leftover 9 Fields. So Each of your 10 different cases got 9 further detailing options. Wich means after two workers set there would be 90 different cases. Then 8 free left and so on.

Maybe I just couldn't properly express what I wanted to say...

Oh sorry, I somehow understood you meant to place only 4 workers of the same color.

However, in this example (two players, two workers each, 10 positions) there are still different placing sequences that end up with the same result.

So you're right with 10*9*8*7 = 5040 different sequences, that lead to only (10*9)/2 * (8*7)/2 = 1260 distinguishable results.

I already devised one. It should be floating around the forum somewhere; if it isn't, let me know and I'll repost it.

Would you really need to do a tree analysis?

Wouldn't you be able to create a serviceable AI by creating a valuation scheme for each of the possible options available and then having the AI take the most valuable space?

A tree is created by calculating how the game will play after taking a specific action. Once the game is calculated out to completion following any given action, only then can you evaluate the value of a that particular action in the present, as compared to all the other actions you have available at the moment [which also have to be calculated to the end game].

The problem as noted by others above is that the tree would get too large to store and take a long time to build and evaluate [for a human to reasonably sit through anyway].

However, without creating a tree, all you'll have is the instant gratification of a certain move. Unfortunately instant gratification doesn't create a strong AI. In Chess, if you played with instant gratification, you'd lose your Queen REALLY quickly.

I've been thinking about this lately, and if I had the time I would probably make a learning agent. I'd create a few guidelines for how valuable certain moves are, then I'd get the agent to play itself a bunch [read: several thousand] of times. It will eventually change all of my ratings on how strong a move is, and come up with it's own set of values. And hopefully in the end, it will have some reasonable skill.

(I originally posted this to my blog, with links. http://gaming.powerblogs.com/posts/1174685639.shtml)

I doubt it will be solved anytime soon (Chess shows no signs of giving up its secrets), I do think a reasonable computer opponent could be developed.

My own technique would be to use some basic genetic algorithms for some decisions, and then use some recent advances in computer Go as a jumping off point.

For example, during worker placement you'll typically have 15 options (Pass, Castle, Gate, Guild, Joust, Stables, Inn, Pass, Spaces 1-n). You mainly can't take occupied spaces, and you can eliminate some obviously bad moves (spaces you won't be able to use, or lose money). Now, if your genetic algorithm (or hardcoded rules) point to a clear decision ... take it. You can also have a clear evaluation function (money, favor, goods are positive ... wasted workers negative, etc etc).

But if you've got 2-3 candidate moves, take each one. Now simulate the turn out, then play out rest of the game 100 (or 200, or 1000) times using random moves for all players. (Possibly keeping the smarts that eliminate completely boneheaded moves). Whichever candidate gives you the best average outcome, take it.

Given how well this works for Go, I think it would be generally applicable.

You'd want to avoid randomly moving the provost (that would probably be hardcoded, and possibly genetic).

My Computer Science theory isn't quite strong enough for me to set up this framework myself (nor do I feel like spending the time) but if a project got started (say, on SourceForge) I may contribute.

I think for Puerto Rico there is this learning excel AI. Maybe something comparable can be created for Caylus too

Ooo, a self-learning autonomous system. You could call it "Skynet". Oh wait, I think Cyberdyne already has that trademarked.

Virtually all game AIs pick the 'best' move available to them. The question is how to determine the 'best' move. If you can calculate the entire game tree, then you know which moves end in victory or defeat. The problem with NOT calculating the whole tree is that you must have a way to assign a value to mid-game positions. The correlation between those values and the actual victory/defeat end condition of that move dictates how well your AI will perform.

With Caylus, there are many fine distinctions in positions that have slightly or wildly different actual values. In the opening, you have to decide if 1 particular resource or 3 deniers is more valuable. That is as *EASY* as it gets. Later you have to weigh dozens of variables all in relation to each other. Are you better off ending the turn with the 25 point blue building + 1 favor + 1 green building, or with the 14 and 7 point blue buildings and 3 favors? That depends on how many turns are left, what your opponent has, etc.