Sonja Elen Kisa
Canada
Toronto
Ontario
-
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
-
Sebastian
Germany
Merzig
Saarland
Thank you for stopping at this OverText. Your cursor is now being scanned for the purpose of security. Please don't move for 3 seconds . . . . . . . . . . . . . . . . . Thank you for your cooperation. You may proceed.
-
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
-
-
TermiGator wrote: 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
In this simplified example, you'll have to go with combinations instead of permutations, i.e., (10*9*8*7)/(4*3*2)=210
-
Panayiotis Zinoviadis
Greece
Ioannina
-
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?
-
Karis Shem
France
Unspecified
Unspecified
-
Unfortunately i don't think IBM (or Microsoft) will be interested enough to put several M$ on this project
-
David Chapman
United Kingdom
Unspecified
-
TermiGator wrote: 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.
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.
-
Maarten D. de Jong
Netherlands
Zaandam
-
Jedit wrote: 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.
-
Nate Cannon
United States
Garland
Texas
I came. I saw.
I lost miserably.
-
cymric wrote: Jedit wrote: 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.
-
David Chapman
United Kingdom
Unspecified
-
cymric wrote: (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.
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.
-
Tristan Brightman
United Kingdom
Bracknell
Unspecified
-
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 
-
Sonja Elen Kisa
Canada
Toronto
Ontario
-
supertris wrote: 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?
-
Sonja Elen Kisa
Canada
Toronto
Ontario
-
Something else we should work on, if it doesn't already exist, is a standard notation system to log games.
-
Mike K
United States
Fairless Hills
Pennsylvania
-
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.
-
Todd McCorkle
United States
Anderson
Indiana
-
What really intrigues me here is the idea of player 1 passing as their first action. Has anyone actually tried this in a game?
-
Tim Seitz
United States
Glen Allen
VA
Like water spilled on the ground, which cannot be recovered, so we must die. But God does not take away life; instead, he devises ways so that a banished person may not remain estranged from him. 2 Sam 14:14
-
kusinohki wrote: 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.
-
Tristan Brightman
United Kingdom
Bracknell
Unspecified
-
Sonja wrote: supertris wrote: 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?
Sorry, no :-( They're all terrible :-p
-
Sebastian
Germany
Merzig
Saarland
Thank you for stopping at this OverText. Your cursor is now being scanned for the purpose of security. Please don't move for 3 seconds . . . . . . . . . . . . . . . . . Thank you for your cooperation. You may proceed.
-
samoan_jo wrote: TermiGator wrote: Your oponent could spend 0-6 people on >10 possible fields. So lets say 4 people on 10 different fields for example that means 10*9*8*7=5040 different possibilities In this simplified example, you'll have to go with combinations instead of permutations, i.e., (10*9*8*7)/(4*3*2)=210
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...
-
-
TermiGator wrote:
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.
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.
-
David Chapman
United Kingdom
Unspecified
-
Sonja wrote: Something else we should work on, if it doesn't already exist, is a standard notation system to log games.
I already devised one. It should be floating around the forum somewhere; if it isn't, let me know and I'll repost it.
-
Tim Seitz
United States
Glen Allen
VA
Like water spilled on the ground, which cannot be recovered, so we must die. But God does not take away life; instead, he devises ways so that a banished person may not remain estranged from him. 2 Sam 14:14
-
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?
-
Graeme Jahns
Canada
Burnaby
British Columbia
-
Quote: 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.
-
Brian Bankler
United States
San Antonio
Texas
Modified Limited Rampage!
-
(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.
-
Klaus Knechtskern
Germany
Groebenzell
Unspecified
-
I think for Puerto Rico there is this learning excel AI. Maybe something comparable can be created for Caylus too
-
Marty Stainbrook
United States
Seattle
Washington
-
BlackTower wrote: 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.
Ooo, a self-learning autonomous system. You could call it "Skynet". Oh wait, I think Cyberdyne already has that trademarked.
-
Clarence Risher
United States
Nashville
Tennessee
-
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.
-
|
|
