Description

1           AI Wargame

AI Wargame^[1] is a 2-player game played by an _attacker (_a) and a _defender (_d) on a 5 × 5 board. A demo of the game is available at https://users.encs.concordia.ca/∼kosseim/COMP472Fall2023/

Each player has 6 units on the board. These units can be of different types:

AI (_A) each player has only 1 AI unit. The goal of the game is to destroy the opponent’s AI.

Viruses (_V) are very offensive units; they can destroy the AI in 1 attack.

Techs (_T) are very defensive units, Tech and Virus are equal in combat against each other.

Programs (_P) are generic soldiers.

Firewalls (_F) are strong at absorbing attacks, but weak at damaging other units.

Each unit has an associated health level, represented by an integer between [0…9]. Initially, all units have full health (9). When the health level of a Virus, a Tech, a Program or a Firewall reaches 0 or below 0, the unit is destroyed and removed from the board. If the health level of an AI reaches 0, then the player loses the game.

1.1          Initial Configuration

At the beginning of a game, the attacker has 1_×AI, 2_×Viruses, 2_× Programs and 1_×Firewall; while the defender has 1_×AI, 2_×Techs, 2_×Firewalls and 1_×Program. The game starts with the following initial configuration:

0        1        2        3       4 A: dA9 dT9 dF9 .                      .
B: dT9 dP9 .                    .         . C: dF9 .                   .           . aP9 D:         .         .           . aF9 aV9 E:          .            . aP9 aV9 aA9	dA9, at A0, represents the defender (d)’s AI (A) and has a health of 9. aP9, at C4, represents the attacker (a)’s Program (P) and has a health of 9. …

The attacker starts the game.

1.2          Actions

Each player take turn to play any of the following actions.

Movement A single unit can move to an adjacent position on the board. Rules to move a unit are the following: 1. The destination must be free (no other unit is on it).

2. Units are said to be _{engaged in combat} if an adversarial unit is adjacent (in any of the 4 directions).

If an AI, a Firewall or a Program is engaged in combat, they cannot move. The Virus and the Tech can move even if engaged in combat.

3. The attacker’s AI, Firewall and Program can only move up or left. The Tech and Virus can move left, top, right, bottom.
4. The defender’s AI, Firewall and Program can only move down or right. The Tech and Virus can move left, top, right, bottom.

Attack A unit _S can attack another unit _T. Rules to attack a unit are the following:

1. _T must be adjacent to _S in any of the 4 directions (up, down, left or right).
2. _T and _S must be adversarial units (i.e. belong to different players).

A combat is bi-directional. This means that if _S attacks _T, _S damages _T but _T also damages _S.

Table 1 shows the damages inflicted to an adversary’s health during a combat.

Health values cannot go above 9 or below 0. If a unit’s health reaches 0, it is destroyed and eliminated from the board.

Repair A unit _S can repair another unit _T. Rules to repair a unit are the following:

1. _T must be adjacent to _S in any of the 4 directions (up, down, left or right).
2. _T and _S must be friendly units (i.e. belong to the same player).
3. The repair must lead to a change of health on _T. Table 2 shows the change in health resulting from repairs. So for example,
   • a Tech cannot repair a Virus (see value 0 in Table 2). This is would be an invalid action.
   • _S cannot repair _T if _T’s health is already at 9. This is would be an invalid action.

Self-Destruct Any unit can kill itself (and be removed from the board) and damage surrounding units.

Self-destruction removes the unit and inflicts 2 points of damage to all 8 surrounding units (if present). This includes diagonals and friendly units. Remember that health values cannot go above 9 or below 0. If the health of a unit reaches 0 or below 0, it is removed from the board.

1.3          End of the Game

The game ends when a player loses their AI, or a pre-determined number of moves has been reached (e.g. 100). A player wins if their AI is alive while the other AI is destroyed; otherwise the defender wins (because the attacker started playing first).

Given that any unit can self-destruct, no player should be left in a position where no action is available to them.

2           Your Task

In this project, you will implement an adversarial search to play the game of AI Wargame automatically. You will implement a minimax algorithm + alpha-beta pruning and at least 2 heuristics.

2.1          Play Modes

Your program should be able to run in manual mode and in automatic mode. This means that you should be able to run your program with:

1. manual entry for both players (i.e. human vs human: H-H)
2. manual entry for one player, and automatic moves for the other (i.e. human vs AI: H-AI, AI-H)
3. automatic moves for both players (i.e. AI vs AI: AI-AI)

After each move, your program must display the new configuration of the board, and some statistics (see Section 2.5).

2.2          Programming Environment

1. You must use GitHub to develop your project so we can monitor the contribution of each team member (make sure your project is private while developing).
2. To program the project, you can use any of the following languages: Python, Java, C, C++. If you wish to use another language, please check with me first (just send me an email). However, note that a significant skeleton of code written in Python 3.11 is available on Moodle. You can use this code as a starting point. If you wish to use another language, you will have to write on your own all the functionality provided in the Python skeleton.
3. If you do choose Python, if you wish, you can use the _PyPy^[2] runtime instead of the regular _CPython to make your code run faster, but be careful as _Pypy is not compatible with all _Python

2.3          The Heuristics

Develop 2 different heuristics, _e1 and _e2, to play this game automatically. For deliverable D2 (see Section 3), you will need to implement and demo your code with the following heuristic:

e₀ = (3V_P1 + 3T_P1 + 3F_P1 + 3P_P1 + 9999AI_P1) − (3V_P2 + 3T_P2 + 3F_P2 + 3P_P2 + 9999AI_P2) where:

V_Pi = nb of Virus of Player _{i   TPi} = nb of Tech of Player _{i              FPi} = nb of Firewall of Player _i P_Pi = nb of Program of Player _{i AIPi} = nb of AI of Player _i

2.4          The Input

It is not necessary to have a fancy user-interface. A simple command-line interface with a text-based I/O is sufficient. As long as your program supports the following input:

2.4.1           Game Parameters

Your program must accept the following game parameters^[3].

1. The maximum allowed time (in seconds) for your program to return a move

Your AI should not take more than _t seconds to return its move. If it does, your AI will automatically lose the game. This entails that even if your adversarial search is allowed to go to a depth of _d in the game tree, it may not have time to do so every time. Your program must monitor the time, and if not enough time is left to explore all the states at depth _d, it must interrupt its search at depth _d and return values for the remaining states quickly before time is up.

2. The maximum number of turns to declare the end of the game (see Section 3)
3. A Boolean to force the use of either minimax (_FALSE) or alpha-beta (_TRUE)
4. The play modes

Your program should be able to make either player be a human or the AI. This means that you should be able to run your program in all 4 combinations of players: H-H, H-AI, AI-H and AI-AI.

2.4.2           Coordinates of Actions

Moves will be specified by the coordinates of the source _S, then the coordinates of the target _T (e.g. _{B2 B3}).

• If the target _T is an empty cell, the action will be interpreted as a movement.
• If the target _T is an adversarial unit, the action will be interpreted as an attack.
• If the target _T is a friendly unit (=_{̸ S}), the action will be interpreted as a repair.
• If _T = _S, the action will be interpreted as a self-destruction.

Coordinates will be specified by the row number (a letter _∈ [_A…E]), then the column number (an integer ∈ [0_…4]); for example, _B3.

If a human player enters an illegal action (e.g. _W3, the coordinates of a position that is not empty, a move of a unit engaged in combat …), then the human will only be warned and be given a chance to enter another move with no penalty^[4].

If your AI generates an illegal action it will automatically lose the game.

2.5          The Output

Your program should generate an output file with the trace of a single game. The name of these output files should follow the format: gameTrace-<b>-<t>-<m>.txt, where b is either false if alpha-beta is off or true if alpha-beta is active; _t is the value of the timeout in seconds; and _m is the max number of turns.

For example _{gameTrace-true-5-100.txt}, is a game trace where alpha-beta is active, the timeout is 5 seconds for each turn, and the game ends after at most 100 turns. The trace should contain:

1. The game parameters (see Section 4.1):
   1. the value of the timeout in seconds _t
   2. the max number of turns
   3. if a player is an AI, whether alpha-beta is _on or _off
   4. the play modes (eg. player 1 = AI & player 2 = H)
   5. in addition, if a player is an AI, indicate the name of your heuristic: _e0, _e1 or _e2
2. The initial configuration of the board.
3. Then, for each action, display:
   • information about the action:
     1. the turn number (eg. _{turn #1})
     2. the name of the player (eg. _Attacker)
     3. the action taken (eg. _{move from C4 to C3})
     4. if a player is an AI, the time for the action in seconds (eg. _{time for this action: 0.4 sec})
     5. if a player is an AI, the heuristic score of the resulting board: (eg. _{heuristic score: -881}) f) the new configuration of the board
   • if a player is an AI, cumulative information about the game so far:
     1. the number of states evaluated by the heuristic function since the beginning of the game (e.g.

Cumulative evals: 18.0M)

1. the same number as above but split over each depth (consider the starting node to be at depth 0)

(e.g. Cumulative evals by depth: 1=39 2=277 3=2.3k 4=17.9k 5=95.4k 6=6.5M 7=11.4M)

1. c) the same number as above but expressed as percentages

(e.g. Cumulative % evals by depth: 5=0.5% 6=36% 7=63%)

4. d) the average branching factor: (e.g. _{Average branching factor: 4.8})

4. The winner of the game (e.g. _{Defender wins in 37 turns})

3           Evaluation Scheme

Students in teams can be assigned different grades based on their individual contribution to project. The team grade will count for 90% and the individual grade will count for 10%.

Deliverable	Deadline	Functionality	%	Evaluation Criteria
D1 + Demo 1	see page 1	manual          game:          H-H (no minimax, no heuristic)	30%	Code (25%): functional criteria (I/O, functionality of the rules of the game, detection of illegal actions, output files …), programming quality. Demo (5%): quality of the presentation, knowledge of the code and clarity of explanations, time management, team QA
D2 + Demo 2	see page 1	same as above + AI moves (minimax, alpha-beta, e0, e1 and e2)	45%	Code (40%): functionality of minimax & alpha-beta (generation and heuristic evaluation of states, return of the best action, …), quality of the heuristics, programming quality. Demo (5%): quality of the presentation, time management, team QA
Tournament	tbd	same as above	5%	Participation at the tournament with a functional code (i.e. no crashing or other functional error). Your ranking at the tournament will not be evaluated, only your participation.
D3	see page 1	same as above + Report	10%	Clarity of the report, justification of the heuristic, depth of the analysis, presentation, grammar, …
Individual			10%	Peer-evaluation done after D1 and D3
grade				Contribution of each student as indicated on GitHub Individual Q/A at demo 1 and demo 2 (correct and clear answers to questions, knowledge of the program, …).
		Total	100%

3.1          Demos

You will have to demo your project after each deliverable. Regardless of the demo time, you will demo the program that was uploaded by the submission deadline. The schedule of the demos will be posted on Moodle. The demos will consist of 2 parts: a presentation and a Q/A part.

Demo 1

□ Prepare a _≈ 5 minute presentation to explain your code and show its functionality.

□ After your presentation, your TA will proceed with a _≈ 10 minute question period. Each student will be asked questions on the code/project, and they will be expected to understand and explain any part of the code. Hence every member of team is expected to attend the demo.

□ At the end of the demo, your TA may ask you to generate output files (see Section 2.5) for specific game parameters (see Section 2.4.1). You will need to generate these files, and submit them on EAS.

Demo 2

□ Prepare a _≈ 5 minute presentation to explain your code and your heuristics _e1 and _e2. Discuss the effect of alpha-beta pruning and the quality of the heuristics. Show actual data to back up your claims.

□ After your presentation, your TA will proceed with a _≈ 10 minute question period. Each student will be asked questions on the code/project, and they will be expected to understand and explain any part of the code and any part of the analysis. Hence every member of team is expected to attend the demo.

□ At the end of the demo, your TA may ask you to generate output files (see Section 2.5) for specific game parameters (see Section 2.4.1). You will need to generate these files, and submit them on EAS.

3.2          Tournament

We will organize an AI versus AI tournament. If you participate and your program does not crash or produces a functional error, then you get 5%. Your ranking at the tournament will not be evaluated, only your participation. More details on the tournament will be posted on Moodle.

3.3          Report

The last deliverable will be a 4-5 page report that describes your heuristics, analyses them with respect to one another and within the scope of the tournament, the effect of alpha-beta pruning on the efficiency and quality of the search etc Show actual data to back up your claims. Also provide an analysis of what you have learned, and a description of what you did right/wrong and what you would change if you were to redo the project today.

4           Submission

4.1          Team Leader

If you work in a team, identify one member as the team leader and make sure this information is indicated in the Groups on the Moodle page. The only additional responsibility of the team leader is to upload all required files (including the files at the demo) from their account and book the demo on the Moodle scheduler.

4.2          Submission Checklist

D1: □ Create one zip file containing your code, and a _README file.

□ Name your zip file: 472 Project ID1 ID2 ID3.zip where ID1 is the ID of the team leader.

□ Have the team leader upload the zip file on EAS as Programming Project Group ₁ / Submission Number ₁. During your actual demo with the TA: □ Generate the output files for the data that the TA will give you.

□ Create a zip file called: _{472 Demo1 ID1 ID2 ID3} where _ID1 is the ID of the team leader.

□ Have the team leader upload the zip file on EAS as Programming Project Group ₁ / Submission Number ₂.

D2:          same as D1, but have the team leader upload:

□ Upload the zip file on EAS as Programming Assignment Group ₂ / Submission Number ₁.

□ Upload the demo output zip file on EAS as Programming Project Group ₂ / Submission Number ₂.

D3:

□ Save your report in PDF format.

□ Name your report: 472 Report ID1 ID2 ID3.pdf where ID1 is the ID of the team leader.

□ Have the team leader upload the zip file on EAS as Programming Project Group ₃ / Submission Number ₁.

Have fun!

[1] Do not bother googling this game, I invented it.

[2] https://www.pypy.org/

[3] You do not need to check the validity of these input values; you can assume that they will be valid.

[4] The point of this rule is to avoid losing a game in the tournament (see Section 3.2) because a human did not transcribe your AI’s action correctly.