|
|
|
MAS Colloquia: A* algorithm
A* Paper Game
Setup
Print out the ‘heuristic-grid’ (the paper with the digit-numbers).
Also print out a numbered ‘grid-paper’ for each player.
Prepare white pieces of paper that fit on the fields. These are to hide the numbers on the heuristic-grid. Also prepare some coloured ones. These are used as blocked fields.
Put the heuristic grid on the table and hide all fields with the white paper or ‘block’ fields using the coloured paper.
Leave open the target field and the field to start, this one you may pick by your own choice.
Hand out the numbered grid papers and a pencil to each player.
You are ready to play.
Aim of the game
Find the shortest way from the start to the target while trying not to check all fields.
Rules
You are not allowed to move diagonal. -> For each field there are up to four neighbours.
Do not cross blocked fields.
Starting the Game
- Make a cross on the starting-field. This one is checked and done.
- Remove the paper of all neighbours of the starting field and make a simple calculation on your grid-paper:
- Write down the number it took you to get here from the start. In this case it is 1.
- Add this number to the digit number printed in the field on the ‘heuristic-grid’. Write down the result in the field.
In the Game
- Look out on your paper for the field which is neither checked nor covered and has the lowest sum of steps and heuristic number.
- Check this field with a cross and uncover it’s neighbours.
- Make the calculation for all newly uncovered fields and start over with step #1.
End of the Game
Either you reach the target (congratulations!) or all fields you have uncovered have been checked. In this case there is no way from the start to the target.
Resources
|
|
The 'heuristic-grid' is your playing ground.
It shows for each field the name and the direct distance to the target.
Download the PDF.
|
|
The 'grid-paper' just showes for each player the name of each field.
On this piece of paper each player will write down his calcutlations.
Download the PDF.
|
|
Using Vectorworks?
Create your own game-grid. Choose size of the grid and target field.
Download the vectorscript-file.
|
References
- Stuart Russell, Peter Norvig:
Künstliche Intelligenz - Ein moderner Ansatz, 2004, Prentice Hall, ISBN 3-8273-7089-2
Weblinks
Architectural Usage
Tutorials and more Information
Author: Georg Munkel
|
