• Join over 1.2 million students every month
  • Accelerate your learning by 29%
  • Unlimited access from just £6.99 per month

Artificial Intelligence - The minimax method.

Extracts from this document...

Introduction

ARTIFICIAL INTELLIGENCE PROJECT


ARTIFICIAL INTELLIGENCE PROJECT

INTRODUCTION

  1. Game Playing

Playing games have always been an attraction of computers, and will probably always be so. Action games where you charge around blowing everything up are one type of game, but we are more interested in this project in examining a more thoughtful game. How do you get a computer to make sensible moves when for our game there are 97 possible positions and a horribly big number of board configurations? Surely we can use the search techniques that we have covered. The problems we have thus far considered have been of the type where the problem is well defined at the beginning and nothing changes during the search. Except for one player games that have no chance involved, such as the game of solitaire, (a game where you have to remove pegs from a board), games involve either chance, or another player's moves or both. In this case we cannot simply search for a solution as the other player will try to block you and games of chance simply will no cooperate!
However, we do not throw away all that we have just looked at in Search. We do need to modify the techniques to allow for opponents.

  1. Generate and Test

One approach to take is to look at the problem as one of generating then testing possible sets of moves. One extreme would be to generate a number of complete sets of moves and then test each of them, taking the best one. The alternate extreme is to generate one move at a time, evaluate each move, take the best, and then generate the next move. Obviously, these do not make particularly ideal solutions.

...read more.

Middle

If DEEP_ENOUGH(CurPosition, Depth)

CUR_BEST: PATH = CurPosition

CUR_BEST: VALUE = EVALFUNCTION (CurPosition, Player)

RETURN CUR_BEST

SUCCESSORS = GenerateMoves (CurPosition, Player)

IF SUCCESSORS is empty:

CUR_BEST: PATH = CurPosition

CUR_BEST: VALUE = EVALFUNCTION (CurPosition)

RETURN CUR_BEST

IF Ply = MAX

Set up a current best class:

CUR_BEST: PATH = NULL

CUR_BEST: VALUE = -LIMIT

FOR ALL SUCC IN SUCCESSORS

RESULT_STATE = MINIMAX(SUCC, Depth +1, OTHERPLAYER(Player), MIN)

IF RESULT_STATE : VALUE > CUR_BEST : VALUE

THEN CUR_BEST = RESULT_STRUCT

CUR_BEST : PATH = CurPosition + CUR_BEST : PATH

RETURN CUR_BEST

ELSE - (Ply = MIN)

Set up a current best class:

CUR_BEST : PATH = NULL

CUR_BEST : VALUE = +LIMIT

FOR ALL SUCC IN SUCCESSORS

RESULT_STATE = MINIMAX(SUCC, Depth +1, OTHERPLAYER(Player), MAX)

IF RESULT_STATE : VALUE < CUR_BEST : VALUE

THEN CUR_BEST = RESULT_STATE

CUR_BEST : PATH = CurPosition + CUR_BEST : PATH

RETURN CUR_BEST

  1. Coding

Since we are not only trying to find an efficient algorithm, there are many coding issues that we can talk about.

At the first sight, we have tried to use our State class with all the information concerning a state in it. This class contained a board (15 * 9 * 8 = 1080 variables) , value of the current position, description of current position and all the utility functions. The advantage of this representation is that the algorithm was straight forward but we have encountered a memory problem. In fact, this representation didn’t allow us to go further than depth 3.

Then, we have tried to keep our class State but to remove the board from it. Actually, our class contained only a path and state value (like algorithm above). We this new representation, we had a board that was used by any state.

...read more.

Conclusion

The optimal method to use is an iterative deepening. Previous searches can be used to guide the next search by searching the previous successful moves first and implementing alpha-beta cutoffs. This method is very useful for games which have a highly variable branching factor. But we will just try to find a relatively good and quick solution. So, we have added to our move generator a sorting part. After, the array of moves is filled, we can just sort the moves in decreasing order considering the value of the position they lead to. So, if the player to play is MAX we use them in that order otherwise (MIN) we take the moves from the end of the array. This optimization allows us to reach without any time out depth 20 (it sometimes reaches depth 25 but in 20% of the games we had a time out end of game).

In this game, we have some highly constrained sequences of moves. A player can do a sequence of moves if he uses some visited positions. In this situation, it is often desirable to extend the search to the outcome of this set of constrained moves whether or not the outcome occurs within the fixed depth. This is called Search to a fixed depth with extensions. To implement this, we could add detection for the case where we previously just detected the depth in the generation of moves. But we could solve this easily by incrementing the depth only when the other player is to play. This technique produced many smart sequenced moves but it could sometimes cause a time out end of game if the search goes too far in a sequence.  

EVALUATION

THIS DOCUMENT WAS DOWNLOADED FROM COURSEWORK.INFO - THE UK'S COURSEWORK DATABASE - HTTP://WWW.COURSEWORK.INFO/

...read more.

This student written piece of work is one of many that can be found in our AS and A Level Electrical & Thermal Physics section.

Found what you're looking for?

  • Start learning 29% faster today
  • 150,000+ documents available
  • Just £6.99 a month

Not the one? Search for your essay title...
  • Join over 1.2 million students every month
  • Accelerate your learning by 29%
  • Unlimited access from just £6.99 per month

See related essaysSee related essays

Related AS and A Level Electrical & Thermal Physics essays

  1. Marked by a teacher

    Sensing project

    5 star(s)

    Equipment * 12V power supply * Wires * Rotary potentiometer * Voltmeter * Fixed resistor * Crocodile clips * Protractor * Pointing device (Lego) Circuit diagrams Method and set-up This circuit is first constructed carefully and for safety reasons without the power supply switched on.

  2. Peer reviewed

    Power generation

    4 star(s)

    Then under high pressure the steam turns the blades of the turbine that then spins the generator producing electricity. Generator: This device is what turns the mechanical energy into electrical energy. The steam turbine provides the mechanical energy to the generator.

  1. Investigating the monitoring systems used on modern day large A/C for detection of specific ...

    The best possible display unit being analogue, as tachometers and machmeters are prime examples. With the use of inductive transducers the speed in relation to revolutions per minute can be achieved. This is due to the engine shaft has apertures (teeth)

  2. silicon project

    and silicates (compounds containing silicon, oxygen and metals). Silicon is the principal component of glass, cement, ceramics, most semiconductor devices, and silicones, the latter a plastic substance often confused with silicon. Pure silicon crystals are rarely found in nature, as natural silicon is usually found as silica (SiO2).

  1. AC Generator

    Glue the pieces to the big block base wood (see diagram). 6. Get the two thing metal pieces (brushes) and bend the tips of one end for each brush. Glue each one down to the base under a slip ring each so that they just touch (see diagram).

  2. PHYSICS &amp;amp;#150;Power generation.

    supplying power of 500 Megawatts with a rotating electromagnet drawing a direct current of 5000 amperes. At a step-up transformer, the voltage is stepped up to 400kV for transmission. The current used varies from time to time but it's kept to a minimum as possible for smaller power losses through the cables.

  1. The Debate Concerning The Age Of Sexual Consent.

    This survey completed by Bliss Magazine also tell us that 50% of it readers think that the current sexual consent laws are correct, but this is most properly sex mad teenagers who want the consent aged to be lowered not for the laws to be tightened.

  2. Sensors Project Report

    The circuit will be set up with other variable resister will have the lowest resistance to make the sensor more sensitive so that it can be accurate and experiment will all be done on the same day to get sensible results.

  • Over 160,000 pieces
    of student written work
  • Annotated by
    experienced teachers
  • Ideas and feedback to
    improve your own work