WhyWritingAWesnothAIIsHard

Overview

I'm largely writing this in response to the number of people who have historically wanted to write a Wesnoth AI, as well as the number of students who are interested in developing an AI for Wesnoth as part of Summer of Code.

Having an AI for Wesnoth is very useful, but one shouldn't underestimate its difficulty. Most traditional AI methods cannot be applied to Wesnoth, so it is necessary to use highly innovative solutions.

Many people think that a very powerful AI for Wesnoth should be fairly easy. After all, computers can beat the world's best players in chess and backgammon, both of which are turned based games, so why not Wesnoth? This document will give an overview of why techniques used in chess and backgammon will not be near as successful in Wesnoth.

Wesnoth's flexibility hurts us

Wesnoth is very flexible. There are many different maps, of different sizes, and different units. Players can even add their own units. This makes it much more difficult to make a general AI.

Computers are very good at chess because chess is played on a relatively small board, that is always the same, and the pieces always start in the same position. This means there are a relatively limited set of positions that the computer has to deal with, and in particular, the types of positions a computer has to deal with are very limited. Patterns such as three consecutive pawns in front of a castled king are common in chess, and so it is relatively easy for a chess evaluation engine to recognize such patterns and evaluate their strength.

Wesnoth is much different. To even compare Wesnoth with chess, you would have to consider a chess program written for a chess game where the board can be any size and shape. It could have impassable squares in the middle. It could have corners that are inaccessible and so forth. Additionally, players could have various 'fantasy pieces' which are defined according to complex rules. Pieces that move like knights, but with extra steps. Pieces that can move likes knights and like bishops, and so forth.

Such a program would not play near as well against skilled humans. Humans could adapt to the new pieces far more readily than a computer program can.

But that still doesn't begin to approach the complexity of Wesnoth. Wesnoth has uncertain information, and random outcomes. Chess programs rely heavily on chess's deterministic nature. Wesnoth is more like backgammon in this way: you don't know what the outcome will be. But, backgammon has a tiny state space, while Wesnoth has a huge one.

Wesnoth's computational complexity

The computational complexity of Wesnoth is immense compared to board games such as chess, backgammon, shogi, and go.

If one considers a 30x20 map -- a typical size for a Wesnoth map -- and one considers 16 standard terrain types. This can be represented in 2400 bits of data. There are thus 2^2400 possible maps of this size. This is without even considering the many combinations of units that can be on the map, in different locations, in different states of health, and so forth. The number of possible positions is truly immense. The state space of Wesnoth certainly easily exceeds 10^1000, and probably 10^10000.

This dwarfs the complexity of even Go, which has a state space complexity of 'only' around 10^171.

The branching factor of Wesnoth is also huge. In most traditional board games, where much computational analysis has been done, typically a player moves one piece, then the other player moves a piece. In Wesnoth, one moves all their pieces, before the other player moves. Wesnoth also typically has many options as to where one can move a piece. It is not uncommon for a piece to have 20 or more tiles it can move to, and for a player to have a dozen or more pieces. Pieces can also choose to attack, and have a choice of weapon to attack with, and so forth. When an attack does occur, there are many possible results, based on number of strikes that land.

The branching factor of Wesnoth is thus also huge. The game tree complexity of Wesnoth is incalculably large. Thinking ahead many moves is difficult.

Wesnoth as a fuzzy game

Discrete analysis fails badly on Wesnoth because, though technically Wesnoth is a discrete game, there are so many positions that discrete analysis techniques fail.

Fortunately, Wesnoth can be treated much like a continuous game, because many positions tend to be very similar to each other. Additionally, unlike discrete board games, it is not common that a very small wrong move in Wesnoth is disastrous.