Reference: This is a school homework. Below explanation is made by the instructor of CmpE 540 in Bogazici University 2021-2022 Spring
Minimax algorithm and alpha-beta pruning are applied to solve competing vacuum cleaners that want to clean a room from dirts.
python <main.py> <search-type > <init-file> <n-actions>
where
- for :
o min-max (no pruning)
o alpha-beta (pruning in MAX and MIN nodes) - determines the depth of the search tree:
Eg. Suppose there are 3 opponent vacuum cleaners which all act optimal:
o If is 5, the search will be as follows: MAX acts, MIN1, MIN2, MIN3 acts, MAX acts, and the search stops, and the utility values after the second MAX
Problem Description The environment is as follows:
- The environment is NxM grid world.
- Each grid in the environment might contain:
o Vacuum cleaner (our agent)
o Enemy vacuum cleaners
o Obstacles that avoid entering to that grid. There is not dirt in the obstacle with grid.
o One dirt - The vacuum cleaners have 6 actions:
o left, right, up, down moves the cleaner one grid, unless that grid is an obstacle.
o suck action that sucks one dirt.
o stop action does nothing.
§ The environment, agent type, locations of the obstacles, dirt, vacuum cleaners (our agent and other agents) will be provided in a text file.
§ Tie-breaker:
o If required, the precedence used as a tie-breaker is as follows: left, right, down, up, stop, suck
§ Opponent vacuum cleaners, which are numbered with even digits, move randomly
§ Opponent vacuum cleaners, which are numbered with odd digits, move optimally
§ Your vacuum cleaner starts first, then other vacuum cleaners (ordered by their digits) move next to each other.
Utility function:
The utility value at any node is calculated as follows: - If your vacuum cleaner is in the same grid with one of the any other opponent, utility is set to -100 and the episode ends.
- Otherwise, utility = (the number of dirts cleaned by your cleaner – the number of dirts cleaned by your opponents)
Example input is like:
where
- x corresponds to obstacles
- c corresponds to your vacuum cleaner
- each corresponds to one of your opponents where
§ even opponents move randomly
§ odd opponents move optimally - . (dot) corresponds to the dirt
Output:
After running the search, you need to print out the following (to standard output):
Action:
Value:
Util calls:
where
• is the optimal action of your agent in its first move
• is the (expected) minimax value of the root node
• is the number of calls for utility function