Dec. 19, 2010
"Settlers of Catan" Victory Prediction From Starting Settlements
game-related, optimization problem, support vector machines, scikit-learn, speedhack
As an introduction project to SVMs and supervised machine learning, this uses AutoHotkey and Cheat Engine's speedhack to observe the computer play thousands of games against itself in Big Fish Games' PC version of Settlers of Catan, it then feeds interesting features into an SVM binary classifier with scikit-learn to predict the winner.
The AutoHotkey script calculates and takes the worse positions so that it's essentially a computer vs. computer game. It records the starting settlement locations for each computer and other influencing factors. The game is ran at high speed with speedhack until completion and the victor is recorded. The Python program uses the captured board game and initial settlement positions to generate a feature vector of interesting properties such as: player's coverage percent of each resource, a representation of their trade potential, and total potential resource value. These features are then normalized, parameters tuned, and an SVM model generated with cross-validation for predicting the winner.
Unfortunately with this project I never achieved much higher than a 50% "by chance" prediction rate. It could be that the AI of this particular PC game simplify nullifies the value of starting positions through optimistic trading and so forth. Alternatively, I may be too inexperienced to correctly select, normalize, and generate useful features, or to tune the SVM parameters.