How do generic game engines work?

Question

The evaluation functions for chess usually includes chess specific knowledge. However, Zillions of Games is able to play any game based only on a description of how the pieces move and winning/losing/draw conditions. And as I see, does quite a good job.

Engines like Fairy-Max can only play chess-like games, which includes many assumptions in its design that do not need to be generalised. But when making a generic game engine (which I dream of doing), the engine simply can't assume almost anything.

I got a nudge in the right direction with the post 'ab-initio' piece values on TalkChess. Yet it does not provide the whole picture.

So, how do generic game engines (like Axiom Development Kit, which is an independent engine that plugs into Zillions; or even the very Fairy-Max) evaluate position?

Edit 1: I found some more information in the 1993 paper by Barney Pell entitled A Strategic Metagame Player for General Chess-Like Games (found it from the "General Game Playing" page on chessprogramming.org).

Answer 1

I don't know about Zillions specifically, but it's a reasonably good strategy in most games to maximise your own flexibility of action while minimising your opponent's. This is certainly true for chess; there are competent chess engines (ie. strong enough to beat an amateur consistently) which use only material value and mobility for evaluation.

The Beale Effect (ie. minimax with random position evaluations) yields a reasonably good chess engine with a modest depth of search, plateauing around 2000 ELO. This relies entirely on a second-order effect of mobility, ie. you're most likely to find the highest random value in a part of the game tree that branches a lot.

I would not be surprised, therefore, to find that Zillions uses either a random evaluation or one based on mobility. The value of a piece, after all, is strongly correlated with its mobility.

Answer 2

Check out the Zillions clone and learn for yourself. http://www.chessv.org/

Even just a simple material eval function beats the majority of players.

Answer 3

In the 1980's I read a book "How to get the most out of your chess computer" by chess master and computer scientist David Levy. It is somewhat dated because engines like Alpha Zero have brought new ways of playing chess. But for a generic chess engine it's still a useful book. Levy explains that engines use a brute force ply search. A ply is one half move: white or black making a move. Then he explained the "horizon effect" which was the main weakness of chess computers at that time; from my games against current generaic engines on sites like FICS [free internet chess site] that are rated approx 2000 I still see The Horizon effect: it means that the engine's ply search ends and it assesses the outcome wrongly, often disastrously. In endgames this was the most common time for it; a human can work out that in 30 moves there's a won endgame by looking at the aspects of the potition rather than calculating. An engine, at least a generic one, can't easily do that. More advanced engines like Fritz or Stockfish find clever ways of beating the horizon effect but that's a whole other discussion.