Lost Cities

Lost Cities is a two-player card game where each player tries to mount profitable expeditions. Like many games designed by Reiner Knizia, it features simple and elegant rules, plays fast, but still has suprising strategic depth. It is currently published by Kosmos, Rio Grande and Devir (among others). You can download the official rules from the Rio Grande web site and check the BoardGameGeek page for reviews, strategy and more information.

This computer implementation allows playing against an artificial intelligence (AI) player. It was written in Haskell using the wxWidgets interface.

Although there are some web-based implementations available with nicer graphics, I wanted something that I could use off-line; another requirement was that it should fit the small screen netbooks (such as my eeePC).


Artificial intelligence

The AI uses a "Monte-Carlo" approach to simulate the hidden draw deck and the opponent's hand by randomly generating several alternative game positions, analysing each scenario using classical minimax with αβ-prunning; finally, the best move on average is choosen.

The high level of abstraction of Haskell allows the code to be quite succint: the game playing module (LostCities.hs) is roughly 400 lines and the whole application is about 1200 lines. Unlike the web-based versions, this implementation is open-source which means that other programmers can verify that the AI does not cheat...


Requires a resonably recent GHC compiler (version 6.8.x or newer) plus the wxWidgets/wxHaskell libraries. This was developed on an Ubuntu GNU/Linux system, and should compile and run fine on other Linuxes. It also compiles and runs on Windows XP but I had reports of failure to run under Mac OS X.


Source code

You can download the latest source package from Hackage; to compile and install use the following shell commands (where x.y is the package version):

tar xvzf lostcities-x.y.tar.gz
cd lostcities-x.y
runhaskell Setup.hs configure
runhaskell Setup.hs build
runhaskell Setup.hs install

Alternatively, you can download and install in one step using the Cabal install tool:

cabal install lostcities


Sorry but I don't have the time to maintain binary packages for diferent operating systems. Nonetheless, I'd be willing to put up links if other people volunteer to do this.


Please contact me you enjoy this game or if you have some suggestion. I'm particularly interested in remarks on how the AI plays and suggestions on how to make better.

Pedro Vasconcelos, pbv at dcc dot fc dot up dot pt
Departamento de Ciência de Computadores
Faculdade de Ciências da Universidade do Porto