Evaluation functions for cutoff search , Computer Engineering

Assignment Help:

Evaluation Functions for Cutoff Search - artificial intelligent

Evaluation functions guess the score that may be guaranteed if a specific world state is reached. In chess, such evaluation functions have been known long before computers came along. Simply, one such function counts the number of pieces on the board for a specific player. A more complicated function scores more for the more influential pieces as queens and rooks: each pawn is worth 1, knights and bishops score 3, queen's score 9 and rooks score 5. These scores are utilized in a weighted linear function, where the number of pieces of a particular type is multiplied by a weight, and all the products are added up. For instance, if in a specific board state, player one has 1 bishop,  6 pawns ,2 rooks ,1 knight and 1 queen, then the evaluation function, for that board state f, B, would be calculated as follows:

f(B) = 1*6 + 3*1 + 3*1 + 5*2 + 9*1 = 31

In bold , the numbers are the weights in this evaluation function (for example , the scores assigned to the pieces).

Preferably, evaluation functions should be fast to calculate. If they take very much time to calculate, then less of the space will be searched in a given time restriction. Evaluation functions should, ideally also match the real score in goal states. This is, Of course not true for our weighted linear function n in chess, because goal states only score 1 for a win and 0 for a loss. Actually  we do not need the match to be exact - we may use any values for an evaluation function, as long it scores more for better board states.

A bad evaluation function may be disastrous for a game playing agent. There are 2 major problems with evaluation functions. Initially, certain evaluation functions just make sense for game states which are quiescent. A board state is quiescent for an evaluation function, f, if f's value is unlikely to exhibit wild swings in the near future. For an  example, in chess, board states such as one where a queen is threatened by a pawn, where1 piece may take another without a similar valued piece being taken back  are  not  quiescent  in  the  next  move  for  evaluation  functions  such  as  the  weighted  linear evaluation function mentioned above. To get around this problem, we might make an agent's search more sophisticated by implementing a quiescence search where  given a non-quiescent state we want to evaluate the function for, we expand that game state until a quiescent state is reached, and we take the value of the function for that state. If quiescent positions are much more likely to arise than non-quiescent positions in a search, then such type of extension to the search will not slow things down very  much. A search strategy may choose in chess, to delve further into the space whenever a queen is threatened to try to avoid the quiescent problem.

It is also bearing in mind the horizon problem, where a game-playing agent can't see far sufficient into the search space. An example of the horizon problem in Norvig  and Russell is the case of promoting a pawn to a queen in chess. In the board state they present, this may be forestalled for a particular number of moves, but it is inevitable. However, with a cut off search at a sure depth, this inevitability can't be noticed until too late. It is likely that the agent trying to forestall the move would have been better to do something else with the moves it had available.

In the card game example above, game began are collections of cards, and a possible evaluation function would be to add up the card values and take that if it was an even number, but score 0 ,if the sum is an odd number. This evaluation function matches perfectly with the real scores in goal states, but perhaps it is not good idea. Suppose the cards dealt were: 10, 3, 7 and 9. If player one was forced to cut off the search after only the first card choice, then the cards would score:  10, 0, 0 and 0 respectively. So player 1 would select card 10, which would be terrible, as this will inevitably lead to player one losing that game by at least 12 points. If we scale the game to choosing cards from 40 rather than 4, we can see that a more sophisticated heuristic involving the cards left un selected may be a better idea.


Related Discussions:- Evaluation functions for cutoff search

Explain error detection and correction codes, Q. Explain Error Detection an...

Q. Explain Error Detection and Correction Codes? Before we wind up data representation in reference of today's computers one should determine about code that helps in correctio

An 8086 interrupt, An 8086 interrupt can take placedue to the following rea...

An 8086 interrupt can take placedue to the following reasons: 1.  Hardware interrupts caused by some external hardware device. 2.  Software interrupts that can be invoked wit

How many and gates are required to realize Y = CD+EF+G, How many AND gates ...

How many AND gates are required to realize Y = CD+EF+G ? Ans. Y = CD + EF + G for realize this two AND gates are needed (for CD and EF).

Explain the number unobtainable tone in strowger telephony, Explain the num...

Explain the number unobtainable tone in strowger telephony with waveforms and the timings. In the following figure illustrates the number unobtainable tone that is continuous

Determine the frequency of the input signal, An eight stage ripple counter ...

An eight stage ripple counter uses a flip-flop with propagation delay of 75 nanoseconds.  The pulse width of the strobe is 50ns.  The frequency of the input signal which can be use

Re:- exam help, Hello there i have 4 exams of ICT and i am after a tutor wh...

Hello there i have 4 exams of ICT and i am after a tutor who can help me in those 4 subjects. One hour for each subjects will be good for me as i have sample papers ready for all s

Observed speedup and parallel overhead, Observed Speedup Observed speed...

Observed Speedup Observed speedup of a system which has been parallelized, is defined as:                             Granularity is one of the easiest and most extensi

Describe about general-purpose registers, Q. Describe about general-purpose...

Q. Describe about general-purpose registers? The general-purpose registers as the name proposes can be used for several functions. For illustration they may comprise operands o

How will you fine-tune a class, How will you fine-tune a class? It is u...

How will you fine-tune a class? It is useful to fine-tune classes before writing code in order to examine development or to improve performance. The purpose of execution is to

Analysis of amdahls law, The outcomes of analysis of Amdahl's law are: 1...

The outcomes of analysis of Amdahl's law are: 1) To optimize the performance of parallel computers, modified compilers need to be developed which should aim to decrease the numb

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd