I have a program that can analyze boards and positiong for a game that me and my friends made up. The only problem is that i cant figure out a good evaluation function, to return the value of a position without actually looking any moves ahead. The computer can look about 15 moves ahead, but if there is no win in sight, it has no clue how to analyze the positions. You play the game on a grid/board of any size, and each player starts in a certain position. You can move up left, right, or down and you scribble in the new square where you go to. You cannot move over already scribbled squares, and if you cant move then u lose. You can also play with teleporters, where when u move into one you come out at another one of your choosing on the board, and there are numerous other variations. Im looking for a way to create an evaluation function, thanx A Mathematical game developed and played excessively by friends and I

you can use an evolutionary algorithm to evolve the weights for a neural network. Seach for work by David Fogel (Checkers), or even better, buy his book Blondie24, which is a great read.



My Website: ai-junkie.com | My Book: AI Techniques for Game Programming

just have it move closer to the player so it limits squares eh cna move to if there is no win in sight, attempt to not lose.

A good evaluation heuristic is one that accurately estimates how good of a position a player is in. In the case of your boardgame, I would suggest that the heuristic simply be how many empty squares are reachable from the AI's location (area of flood-fill) and how many are reachable from the opponent's location. Subtract the second from the first, and use that as the move's "score".

How appropriate. You fight like a cow.

[edited by - sneftel on September 21, 2003 11:02:57 PM]

Overkill fup!

Check out Policy/Value iteration.

Timkin

A variation of Sneftel''s evaluation:

Try using a ratio rather than a difference. So you would have (myAvailableSquares / hisAvailableSquares).

This can sometimes work better. I wrote AI for a similar game, and in it I used 2 evaluation functions depending on the situation. Basically there was an agressive function for when the AI was winning and a defensive function for when the AI was losing. In your game you might have something like (below is VB code):

If my.squares = 0 Then Eval = -INFINITY: Exit FunctionIf his.squares = 0 Then Eval = INFINITY: Exit FunctionIf strat = AGGRESSIVE Then    Eval = my.squares / (2 * his.squares)Else    Eval = (2 * my.squares) / his.squaresEnd If

So if you have no squares, you''ve lost, this is really bad, and you evaluate to -infinity. Likewise for your oponent.

If you are agressive, you weight your oponents squares in the ratio, making your AI want to make moves that will lower your oponents options, basically kicking him while he''s down.

If you are defensive, you weight your squares in the ratio, making your AI want to make moves that will increase your options, struggling for survival.

----

I haven''t actually played your game yet So I hope this still applies.

Jason

Actually no, srry about the vagueness of the post. The rules I posted were the original game that me and a couple of friends developed, but it developed to a much harder and anti-computer friendly game, (My friends were sure of that, knowing that I like to program ). But anyway, I must have been somewhere else when i was writing this, because these were the rules I meant to write:

The game is played on a 5x5 grid, (or larger, for harder/longer games.) Each player starts in an opposite corner. Each turn, you spend the first half of your turn moving up, left, right or down, like the other game I posted. Then you scribble in that square, and it cant be used again. For the second half of your turn, you get to move to any square on the board. At first this seems to make the game not fun, but it intensifies the logic 100 fold. All of me and my chess buddies play strategy and logic games alot, although this one is posing a very tough problem to solve. The same death rule applies as before, if you cant move then you lose.

This has proved extremely hard for me to find an evaluation function for, because the board is so incredibly dynamic. If someone has not already lost, then on their next move they have access to almost every square on the board. I have some theory behind our games, as in safe squares (a square with two or more exits, so an enemy cant move next to you and thus kill u), power strips (strips already blocked off from the rest of the board 5 spaces long, where one player takes a square 1 space in from the edge of the strip and is thus next turn able to exit the strip and destroy the power strip, or exit the square and keep the safe square). Click the post in my Sig for more info.

If there are any other ways, rather simplistic, I dont think Im ready for neural nets yet, I would be very open to them.

Thanks in advance, Cory

What happens if both players want to move to the same spot on the board (this assumes they move simultaneously)? If the move alternately, then the player moving second has the advantage.

Timkin

Maybe a bit of a stretch but:

You could use a Evolutionary Programming to create an evaluation function.

You would do this by trying to map many known ''good'' boards to a good score, and many known bad boards to a bad score.

ie: You have a board that you know (from your own experience) leaves the player in a good position. You would associate a good score with this board. It would be up to your classifier to determine the relationships between the different boards you provided and their respective scores. Hopefully the system would continue to work with boards it has never seen before.

Best of luck,
Will

If you can''t find a good evaluation function, try random numbers. It''s not a joke, it really works. Random evaluation captures some strange version of mobility when you apply a mini-max search. The idea is that if in a position you only have one non-losing move and in another position you have ten of them, chances are that the maximum of the ten random values will be higher than the single random value that would be the evaluation of the first board.

You also get very varied play (of course), which is fun. I did this for losing checkers (the player that cannot move wins), and it works great.

I am currently reading the book "On Numbers And Games", by Conway. I''ll try to see if I can apply their techniques to your game. There might be a chance there. I''ll post again if I find something interesting.