Write an accurate evaluation function for a Snakes and Ladders game

Instructions

Given the following board,

, determine the percentage chance that a player will win.

Rules of the game

1. One six sided dice!
2. Two players take turns rolling the dice and moving their pieces by increasing the position of their pieces by the number rolled on the dice. (Bonus points to evaluation functions that can take into account more than two players.)
3. If the piece lands (stops) on:
• a snake's head, the piece must be relocated to the snake's tail.
• the bottom of a ladder, the piece must climb up to the top of the ladder.
• the top of a ladder or the tail of a snake, nothing else happens.
4. A player can kill another player if his piece is on the other's at the end of his turn. (Not literally of course.) 'Dying' results in a player having to restart at position 0.
5. If the player rolls a number which would cause his piece to move off the board, they stay where they are and the play passes on to the next player.
6. The player that reaches 100 first wins.

Rules of the contest

Restrictions

• The aggregated bit-length of your constants cannot exceed 100000 bits.
• Your evaluation function cannot, on average, take a hundred times longer than a simulation.
• Your evaluation function cannot run 'probabilistic simulations'.

Other

• If `eval(p,b)` is the evaluation function, it should return a value between `0` and `1`, where `0` indicates it is impossible for player `p` to win, and `1` indicates it is absolutely certain player `p` will win for a given board `b`.

Scoring

(As in the scoring of answers. ;))

The winning evaluation function is able to correctly evaluate the probabilities with the least percentage error on the basis of the averaged (mean) results of 100 simulations run per board on a total of 10 randomly generated boards. (By 'randomly generated board', I mean the players' pieces are in different positions... not the snakes or ladders!)

``````var test_board(player, postions)
{
var player_wins;

repeat(100)
{
// If player wins a game, increment player_wins.
if(run_game(positions) == player)
player_wins += 1;
}

return player_wins / 100.0;
}

var run_simulations()
{
var stack[];

repeat(10)
{
var positions[] = {random(101), random(101)};

stack.push(abs(test_board(positions) -
eval(PLAYER_A, positions)));
}

return stack.average();
}
``````

Please post the inputs and results of your tests! (A table listing the ten different boards used, their evaluated and average values, times taken, and average percentage error.)

-
Rule 1: how? Rule 2: what's the rest of the sentence? Does "No lookup tables" preclude building them in the code? How about searches which aren't depth-first? – Peter Taylor Jan 3 '12 at 8:29
How can you test the results by simulation? Suppose you have the perfect evaluation function. Even this function yields an error and might loose against any other function. – Howard Jan 3 '12 at 8:51
@Howard Run an infinite amount of simulations then to prove your point. (As long as `infinity >= 100`.) – muntoo Jan 3 '12 at 9:10
@PeterTaylor That would still be a lookup table. (Let's make it so the total size of your constants cannot exceed `100000` bits, if you want to be smart about it. :)) – muntoo Jan 3 '12 at 9:25
@muntoo, I'm not trying to be "smart": I'm trying to clarify the spec so that I don't waste time writing a solution which I think it valid but you don't. A limit on the constant size is much better, and I suggest you amend the question accordingly. (After all, taking the current spec literally we can't even encode the board). As it stands, though, it's a pretty boring problem: build a Markov transition matrix, square it a few times for convergence, job done. – Peter Taylor Jan 3 '12 at 9:33