quote: Original post by Timkin
I can provide some references if you like.

Sure, I''m always interested...

A strong evaluation -vs- deeper search is like a tug of war.

If you had a perfect evaluation, you would not need a search. The evaluation would always return the best move possible. The problem here is that nobody knows what the perfect evaluation function is for most games.

So, assuming we don''t have a perfect evaluation function: Typicallly the better the evaluator, the more cpu cycles are required for it to work. In these cases, it is a trade off-- Maybe those CPU cycles would actually let you search deeper in the same amount of time? And that kind of defeats the purpose right, because your evaluator is supposed to let your search go deeper in a smaller amount of time.

Of course It really all depends on what you''re doing. Every game is different. In Chess, I think most people keep their evaluator simple (err, I probably mean fast) and hope for deeper searches. My chess engine keeps it''s evaluator VERY simple, because, after all, my rules are just ''general'' rules, and can never really capture any real meaning.

Will

Whats evaluation and search - what are you talking about - is this like finding the best move in chess - hasn''t this already been done if u give the comp long enough? I would love to know where you get a glossary of all of these terms and a very brief summary to all the keywords.

cuchulainn@msn.com

Thanks for the replies all - been away for a couple of days so haven''t been able to respond sooner unfortunately.

Grbrg - yup I realise that one can try to get a machine to ''learn'' to evaluate states, but I was wondering why most programs don''t bother evaluating very precisely.

Timkin - your post cleared up a lot thanks. I only mentioned the ''perfect'' evaluation function since tuita questioned that assumption - I''m not wondering why we don''t actually have them for large games. What I was asking was why more in-depth state evaluation is usually sacrificed for searching more of the tree. From your post, I gather that the basic reason is that search is just easier in most cases - generating a better evaulation function is just too much work after you''ve got it to a certain level.

RP - that''s been my observation, but I wasn''t sure why people almost always made the trade-off to greater search.

The conclusion seems reasonable, although I''m wondering why humans are so good at evaulation then when we aren''t specifically designed for a particular problem. There have to be better ways of learning than those currently being used.

quote: Original post by grbrg
Sure, I''m always interested...

A good place to start would be:

Madani, Hanks & Condon: On the Undecidability of Probabilistic Planning and Infinite-Horizon POMDPs. AAAI-99, pp541-548

Also:

Hansen, E. A.: Solving POMDPs by Searching in Policy Space. UAI-14, 1998, pp211-219

Parr, R. & Russell, S.: Approximating Optimal Policies for Partially Observable Stochastic Domains. IJCAI-95, pp1088-1094


There are tonnes of other papers, but these are a good starting place...

Cheers,

Timkin

Chuchulain: An evaluation function is merely a black box. There are actually two different types of evaluation functions being discussed in this thread, so I can see how it would be confusing.

In games like Chess, the evaluation function is a form of utility (value) function, which, given a game state (arrangement of the pieces) returns a value of that state relative to all other possible states. You can instantly see the difficulty here in that since there are an almost inumerable number of states, you cannot come up with an exact (perfect) evaluation function, but rather only guess at how good the state is relative to other states. This preference structure over states at some future horizon of moves (say 4 moves ahead) implies a preference structure over the plans (sets of actions) that lead to those states. Thus a player being able to evaluate the quality of possible future states of the game can choose the current move that leads to the best state at the horizon. Another problem arising from this is that optimising the value function at the horizon does not imply that you''ve optimised the value function at the end of the game. That is, you might force yourself down a path of the search tree that offers a significantly lower chance of winning the game, all because it offered a temporarily good intermediate state in the game.

The other form of evaluation function is a black box that, given a state, returns a move (action). Any thoughts of utility or value are hidden inside the box. Such functions can be learned with techniques from reinforcement learning (supervised learning) or sometimes through unsupervised learning techniques. An agent employing such a function would be a reactive agent and the box is sometimes known as the agent function , particularly in the robotics community.


Argus: I hope my explanation above of utility/value functions helps you see the trade-off better. The closer your horizon is to the end state of the game, the weaker the evaluation function needs to be because, ultimately, if you can search to the end of the tree, the preference of states (and thus plans) is given by the win-loss value of the game. For two given finite horizons though, that are both some distance from the end state, it is difficult to discern which is actually closer to the end state. So, rather than try, simply look at how much computational power you have, choose an easy (cheap) to evaluate function and search as deep as you can in a reasonable time (i.e., as long as you can before you think your opponent is going to get up and leave)!

Cheers,

Timkin

Ahh now I see.. the fact that the game''s own evaluation function to decide who wins can be used escaped me. Thanks again Timkin.

I wrote a reasonably successful chess program (Ruy-Lopez) with a very complex evalutation function. That makes the program very slow, but you can control how it plays a lot better, and you can taylor the style to be more "human". Modifying the evaluation function to "teach" something to your program is a lot of fun!

I read Blondie24 (a good read), and I can''t agree with fup in that it achieved "world class ranking" (and I think it was 200 generations). They didn''t try the program in tournaments or agains hand-made evaluation functions. It was an interesting experiment, though. Oh! And the search sucked! There''s nothing wrong with that, because good search wasn''t the goal of the project, but I doubt that a checkers program can be good at around depth 6. I also wrote a (Spanish) checkers program, and the depths are more like 14.

Nice Alvaro - how do you think Ruy-Lopez (if that is the name and not just the opening it used) compared to searchers?

quote: I read Blondie24 (a good read), and I can't agree with fup in that it achieved "world class ranking" (and I think it was 200 generations). They didn't try the program in tournaments or agains hand-made evaluation functions.

I just knew someone would make me go and check! ;0) Let me go get the book...

Okay, you are correct about the number of generations (the final network took 250). I have no idea where I got 70 from. Whatever, 250 is still not very many at all when discussing evolutionary algorithms (which often run for thousands or tens of thousands of generations)

Fogel's program was ranked in the top 500 players registered with zone.com - out of a total of 120,000 players. I must have been so impressed with that I remembered it as a world class ranking. Doh! B24 achieved a rating of 2045, which is "Expert" level officially. I think this is still incredibly impressive though, given the conditions for the experiment.

Also, I'd like to point out that the purpose of the Blondie24 experiment was not to produce a world class player. It was a test to see if an evaluation function could be evolved using just win-draw-loss information. That's why the search wasn't state-of-the-art and that's why they never entered it into any serious tournaments (The book does mention a couple of online tournaments it entered though. I think it won one of them).

Anyhow, sorry I was over enthusiastic about the results but I'm getting old, and my memory is fading...

(although not as old as some, eh Steve, Geta? )






ai-junkie.com

[edited by - fup on October 10, 2002 8:29:25 PM]