• 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)

    The rotary potentiometer will be connected to the circuit by two of its three terminals. A wire coming from the power supply through the fixed resistor connects to the first terminal. Then the second terminal is connected to the voltmeter, which is connected in parallel to the component, which is the rotary potentiometer.

  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. silicon project

    into large quantities often develop a serious lung disease known as silicosis. Explain table Atomic Radius: A measure of the size of an atom, assuming the atom has the shape of a sphere. Slide 6 Silicon is a very useful element that is vital to many human industries.

  2. AC Generator

    Connect wires from the 2 brushes to a galvanometer. Spin from any side with an electric hand drill. Record the current reading. 11. Now move the side magnets 5 cms away from their original position relative to the armature and test it. Record the current reading. Then move them 2 cms towards the armature from their original position and test it.

  1. 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.

  2. Sensors Project Report

    Then results can be recorded. The experiment is done 3 at least 3 times, and then produces a calibration curve. Variables - A variable resistor which will affect the sensitivity of the whole experiment - Number of pieces of paper varies from 1 - 200 pieces and is measured

  1. Sensor Project

    Results - Calculation of R1: I want my amplifier to activate at 10�C, for the heater to come on. The amplifier turns on at 1.93V, as I have tested, and because the voltage is proportional to the resistance, I will work out which resister to use using the equation below.

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

    A system contains essentially of a vibration pick - up unit mounted on the engine at right angles to the axis, an amplifier monitoring unit and a moving coil microammeter calibrated to show vibration amplitude in thousands of an inch.

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