Ida* search-artificial intelligence, Basic Computer Science

Assignment Help:

IDA* Search-Artificial intelligence:

A* search is a sophisticated and successful search strategy. yet, a problem with A* search is that it might  keep every states in its memory, so memory is frequently a much bigger consideration than time in designing agents to undertake A* searches. We solve  the same problem with breadth first search by using an  IDS, and we do similar with A*.

Like IDS, an IDA* search is a series of depth first searches where the depth is increased after every iteration. yet, the depth is not measured in terms of the path length, like  it is in IDS, but rather in terms of the A*  collect function f(n) as described above. To do this, we have to define contours as regions of the search space containing states where it is below some restriction for every the states, as shown pictorially here:

 

2348_IDA- Search-Artificial intelligence.dib

 We see that we could discard M2 straight away, so saving ourselves 3 nodes in the search space. We could reject M3 after we came across the nine, and in the end M4 turns out to be better than M1 for player one. In conclusion, using alpha-beta pruning, we ignored looking at 5 end nodes out of 16 - around 30%. If the calculation to assess the scores at end-game states (or estimate them with an evaluation function) is computationally costly, then this saving could enable a greatly larger search. In addition, t his kind of pruning may occur anywhere on the tree. The general principles are that:

1. Given a node N which may be decide by player one, then if there is another node, X, along any path, likewise that (a) X may be chosen by player two (b) X is on a higher level than N and (c) X has been shown to guarantee a bad score for player one than N, then every the nodes with the same parent as N may be pruned.

2. Given a node N which may be selected by player two, then if there is a node X along any path such that (a) player one may select X (b) X is on a higher level than N and (c) X has been shown to guarantee a better score for player one than N, then every nodes with the same parent as N can be pruned.

As an quection which of these principles did we use in the M1  - M4  pruning example above? (To make it simple, I've written on the N's and X's).

Because we may prune using the alpha-beta method, it makes logic to perform a depth-first search using the minima principle. Compared to a breadth first search, a depth primary search will get to goal states early, and this information may be used to determine the scores guaranteed for a player at specific board states, which used to perform alpha-beta pruning. If a game-playing agent used a breadth first search instead, then only accurate at the end of the search would it reach the goal states and start to perform minima calculations. Thus, the agent would miss much potential to perform pruning.

Utilize a depth first search and alpha-beta pruning is sensitive to the order in which we try operators in our search. In above example, if we had selected to look at move M4 first, then we would have been able to do more pruning, due to the high minimum value (11) from that branch. Regularly it is worth spending some time working out how best to order a set of operators, as this will really increase the amount of pruning that can occur.

It's clear that a depth-first minimax search with alpha-beta pruning search dominates minimax search alone. Actually, if the effective branching rate of a typical minimax search was b, then using

Alpha-beta pruning will decrease this rate tob. In chess, this means that the valuable branching rate reduces from thirty to around six, meaning that alpha-beta search may look further moves ahead than a normal minimax search with cutoff.

Each node in a contour scores less than a specific value and IDA* search agents are told how much to increase the contour limit by on each iteration. This defines the depth for successive searches. When using contours, it is valuable for the function f(n) to be monotonic,for example , f is monotonic if whenever an operator takes a state s1  to a state s2, then f(s2) >= f(s1). In other words, if the value of f always increases along  a path, then  f  is  monotonic.  As an exercise,  why do  we want  monotonicity to ensure optimality in IDA* search?


Related Discussions:- Ida* search-artificial intelligence

Flowchart, create a flowchart showing average score for the 3 quizzes assum...

create a flowchart showing average score for the 3 quizzes assume that there are 3 sections each having 5 students the only valid number to be entered is 1-100 for the quizzes shou

With an example, Question 1 With an example, illustrate the concept of ext...

Question 1 With an example, illustrate the concept of extern variable Question 2 What is the difference between pointer variable and simple variable? Question 3 Give the

Flowchart looping, create a flowchart showing average score for the 3 quizz...

create a flowchart showing average score for the 3 quizzes assume that there are 3 sections each having 5 students the only valid number to be entered is 1-100 for the quizzes shou

Java Assignment, Hi? are you conversant with Java that is J2SE 6 coz i have...

Hi? are you conversant with Java that is J2SE 6 coz i have assignments on this area?

Product of first n natural numbers-algorithm, Product of first n natural nu...

Product of first n natural numbers - Algorithm Working Procedure : 1. Take n = 8 2. Take I = 1 3. Take PROD = 1 4. Compute PROD = PROD * 1 5. add 1 to 1 6. If I≤ n, complete

Spreadsheet software , Spreadsheet Software : Consider the grid in Fig. ...

Spreadsheet Software : Consider the grid in Fig. 9.4. It is split into rows and columns and is a pictorial representation of a typical spreadsheet program.  Figure: Spr

HOMEWORK 9.., AsBased on Chapter Review Problems from the book. 1 #1. Wh...

AsBased on Chapter Review Problems from the book. 1 #1. What is meant by data independence? Explain your answer. #2. Identify two benefits of separating application software fr

DR Racket program, Hi, I''m looking for someone to help me with Computer Sc...

Hi, I''m looking for someone to help me with Computer Science ASAP. How soon are you available? Thanks! Specifically using the Racket program dealing with creating a list that will

Browser cookies, Browser Cookies: A cookie is a small message sent by ...

Browser Cookies: A cookie is a small message sent by the Web server to a your web client. This message is stored by the browser as a text file. The basic purpose of cookie is

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