The Tao of Gaming

Boardgames and lesser pursuits

“Solving” Caylus

There’s a BGG thread about solving Caylus. While 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, consider each one. 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.

Advertisements

Written by taogaming

March 23, 2007 at 5:33 pm

Posted in Artificial Opponents, Caylus

Tagged with ,

One Response

Subscribe to comments with RSS.

  1. I agree and mentioned a similar approach in that thread.

    out4blood

    March 27, 2007 at 6:07 pm


Comments are closed.

%d bloggers like this: