Introduction to Artificial Intelligence

Assignment 2

Playing simplified RISK against an opponent

In the second exercise you will address the issue of an opponent that cannot be predicted in advance. In the first part of the exercise, you will use the same rules of the game as in the first exercise, i.e. the rules of the full version of the game simplified as in the first exercise. However, this time you must be prepared for an intelligent opponent that can reason and search. Basically, you will attempt to play optimally in the sense of minimax. In this exercise, the goal is to win - how fast is secondary.

In the second part of the assignment, the rules of the game change: battles will be decided by the dice, as in the original game of RISK. However, to simplify matters, the battle continues until the attacker wins (and conquers the attacked territory), or has only 1 army left in the attacking territory (essentially losing the battle). Thus, there is no decision needed by the agent on whether to continue a battle.

Implementation Steps

If you did your job well for the first exercise, you will have in place much of the software needed for this exercise, and will just need to change the search algorithm. You should still use your environment simulator to allow for substituting different agents and scoring your agent. Use the following steps:

  1. Write a minimax alpha-beta pruning algorithm for this game.
  2. Develop a static heuristic evaluation function.
  3. Add A/B pruning to improve search depth reachable in reasonable time.
  4. Play some games using your agent against a human, against your other agents, and against itself, and report results.
  5. Begin step 2 - add the dice into the game.
  6. Modify your search algorithm into expectiminimax, change your heuristic if needed, and test your agent.

Clarification

This paragraph should explain what I meant in class by "limiting the branching factor for the randomized element" (added by request). The problem was that the branching factor for a complete battle is huge since it involves numerous die rolls. Instead, when performing search, your program should assume that there is only a small bounded number of outcomes for a battle. For example, we can assume that for a battle of A attackers against D defenders, there are 3 possible outcomes:

  • A and D lose the same number of armies - this outcome has a probability of 0.5. If A is sufficient to win (2 or more greater than D) then D loses all its armies. Otherwise, their loss is such that each has at least one army left after the battle (but still equal losses).
  • A loses 50% more than D. This outcome has probability 0.2.
  • A loses 50% less than D. This outcome has probability 0.3.

    Note that in the last 2 outcomes, you should appropriately truncate so that the rules are obeyed. For example, in the 2nd case, if A has 10 armies and D has 4, then D loses all and A loses 6 (and wins the battle). However, if A has 10 and B has 8, then since A cannot lose 12, it loses just 9 (the maximum it can lose when attacking), and B loses only 6.

    Note that when the battle actually occurs, the original RISK rules apply w.r.t. die tosses - it is only when reasoning about the battle that the simplified limited branching scheme above is used!

    Deliverables

    The program and code sent to the grader, by e-mail or otherwise as specified by the grader, a printout of the code and results. Set up a time for frontal grading checking of the delivered assignment, in which both members of each team must demonstrate at least some familiarity with their program...

    Due date: December 4. Postponed to December 11.