Minmax search - artificial intelligence, Computer Engineering

Assignment Help:

MinMax Search

Parents frequently get two children to share a cake by asking one to cut the cake and the other to select which half they want to eat. In this two player cake-scoffing game, in only one move (cutting the cake) player one soon learns that if he wants to maximize the amount of cake he gets, he had to cut the cake into equal halves, because his enemy is going to try and minimize the cake that player 1 gets by selecting the biggest half for her.

Imagine we have a two player game where the winner scores a positive number at the end, and the loser scores nothing. In board games such as chess, the score is normally just 1 for a win and 0 for a loss. However, in other games such as poker one player wins the (cash) amount that the other player loses. These all are called zero- sum games because when you add one player's winnings to the other player's loss the sum is zero.

The minima algorithm is called because it assumes that you and your opponent will be  act rationally, and so you will select moves to try to maximise your final score and your opponent will choose moves to try to minimise your final score. It is helpful to have a game where the search tree is small to demonstrate the minima algorithm.  This is the reason for invent the following very trivial game:

Take a pack of cards and deal out 4 cards face up. 2 players take it in turn to select a card each until they have 2 each. The object is to select  2 cards so that they add to an even number. The winner is the one with the biggest even number n (picture cards all count as 10), and the winner scores n. If both of the players get the same even number, it is a draw and both score are zero.

Imagine the cards dealt are 3, 7,5 and 8. One should choose first in which card player he has interest and the minima algorithm can be used to decide this . To demonstrate this, we will draw the whole search tree and put the scores below the final nodes on paths which represent particular games.

765_minmax search.png

Our goal is to write the best score on the top branches of the tree that player one can guarantee to score if he chooses that move. To do this in the starting at the bottom, we will write the concluding scores on successively higher branches on the search tree until we reach on the top. Whenever there is a option of scores to write on a specific branch, we will assume that player 2 will choose the card which minimises player one's final score, and player 1 will select the card which maximises his/her score. Our aim is to move the scores all the way up the graph to the top, which will make possible for player one to choose the card which leads to the best guaranteed score for the overall game. We will initial write the scores on the edges of the tree in the bottom two branches

 We want to move now the scores up to the next level of branches in the tree. But there is a option. For example, for the first branch on the second row, we could write either 10 or 12. This is where our assumption regarding rationality comes into concern. We should write 10 there because imagine what player 2 has in fact chosen the 5, and then player 1 can choose either 7 or 8. Selecting 7 would result in a score of 10 for player 1, selecting 8 would result 12. Obviously player 1 would select the 7, thus the score we write on this branch is 10. Hence, we should select the maximum of the scores to write on the edges in the row above. we get the following by  doing the same for all the other branches:

770_minmax search1.png

In the final we want to put the scores on the top edges in the tree. there is a choice again . In this type of case, however, we have to remember that player 2 is making the selection, and they will act in order to minimise the score that player 1 gets. Thus, in this case when player 1 chooses the 3 card, player 2 will choose the 7 to minimise the score player 1 can obtain. Hence, we select the minimum possibility of the 3 to put on the edges at the top of the tree as follows:

775_minmax search2.png

To select  the right  first card, player 1 simply looks at the topmost edges of the final tree and select  the one with the highest score. selecting  the 7 ,In this case, will guarantee player 1 scores 10 in this game (assuming that player one select  according to  the minima method for move 2 but-essentially - making  no assumptions about how player 2 will choose).

876_minmax search3.png

Notice the above process was in order for player 1 to choose his/her first move. The complete  process would need to be repeated  again and again for player two's first  move, and player one's second move, and so on . Agents playing games, in general, using a minimax search have to calculate the best move at every particular stage using a new minimax search. Donot forget that only  because an agent thinks their opponent will act rationally, doesn't  mean  they  will act rationally,  thus  they  cannot  assume  a  player  will  make  a specific  move until they have actually done it.


Related Discussions:- Minmax search - artificial intelligence

How many ram chips are required for memory of 2048 bytes, How many 128 × 8 ...

How many 128 × 8 RAM chips are required to provide a memory capacity of 2048 bytes. Ans. Available here RAM chips = 128 x 8 Required the memory capacity    = 2048 x 8 No. of chip

What is input-output processors, Q. What is Input-output processors? le...

Q. What is Input-output processors? let's briefly summarize the development in area of input/output functions. These can be briefed as below: 1. CPU directly controls a peri

What is the main use of structures, What is The main use of structures ...

What is The main use of structures The main use of structures is to lump together collections of disparate variable types, so they can conveniently be treated as a unit. For ex

What are desirable features of an electronic market place, What are the des...

What are the desirable features of an Electronic Market Place? Features of an Electronic Market Place: 1. Its electronic and business center is not a physical building qu

Predictive modelling power, Another useful feature of an experts system ...

Another useful feature of an experts system is its predicative modelling power. The system can act as an information processing theory or model of problem solving in th

Blocking and non-blocking network, Blocking and Non-Blocking network In...

Blocking and Non-Blocking network In non-blocking networks the route from any free input node to any free output node can always be offered. Crossbar is an best example of non-

Major characteristics of a computer family, Q. Major characteristics of a c...

Q. Major characteristics of a computer family? Let us summarise the major characteristics of a computer family. These are as below: Figure: Characteristics of computer

How does multiplexer know which line to select, How does multiplexer know w...

How does multiplexer know which line to select? This is managed by select lines. The select lines provide communication among different components of a computer. Now let's see

Explain about the view selection problem, Often calculating all the data is...

Often calculating all the data is not possible by aggregations for this reason some of the difficult data problems are solved. In order to verify which data should be solved and me

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