2023年11月25日

Python代写AI | COMP30024 Artificial Intelligence Project Part A

Project Part A

Searching

COMP30024 Artificial Intelligence 2021

In this first part of the project, we will play a simplified, single-player (non-adversarial), search-based variant of the game of RoPaSci 360. Before you read this specification, please make sure you have carefully read the entire ‘Rules for the Game of RoPaSci 360’ document.

The aims for Project Part A are for you and your project partner to (1) refresh and extend your Python programming skills, (2) explore some of the algorithms you have met in lectures, and (3) become more familiar with some core mechanics of RoPaSci 360. This is also a chance for you to develop fundamental Python tools for working with the game: Some of the functions and classes you create now may be helpful later (when you are building your full game-playing program for Part B of the project).

Single-player RoPaSci 360
The single-player game we will analyse is based on RoPaSci 360, with the following modifications:

  1. There is no throw action. Instead, the game begins with tokens already on the board.
  2. Lower’s tokens never move. On each turn, all of Upper’s tokens move (each using a slide or swing

    action), all at the same time. If Upper has more than one token, they all move at the same time.

  3. The player must repeatedly move the Upper tokens to defeat all of Lower’s tokens to win. If the last Upper token is defeated in the same turn as the last Lower token, the player still wins.
  4. There is a new type of token: Block tokens prevent other tokens from occupying their hexes. Block tokens never move. No token can slide or swing onto or over a Block token.

Most of the other rules (for example, the rules for slide and swing actions, and the rules for token battles on shared hexes and defeating tokens) are the same as in the original RoPaSci 360 game.

The tasks

Firstly, you will design and implement a program that ‘plays’ a game of single-player RoPaSci 360. That is, given a starting board configuration, the program must find a sequence of actions to win the game (to defeat all Lower tokens). Secondly, you will write a brief report discussing and analysing the strategy your program uses to solve this search problem. These tasks are described in detail in the following sections.

The program

You must create a program to play this game in the form of a Python 3.6 module1 called search.
When executed, your program must read a JSON-formatted board configuration from a file, calculate a winning sequence of actions, and print out this sequence of actions. The input and output format are

specified below, along with the coordinate system we will use for both input and output.

Coordinate system

For input and output, we’ll index the board’s hexes with an axial coordinate system2. In this system each hex is addressed by a row (r) and column (q) pair, as shown in Figure 1.

Input format

Your program must read a board configuration from a JSON-formatted file. The name of the file will be given to your program as its first and only command-line argument.3 The JSON file will contain a single dictionary (JSON object) with the following three entries:

• An entry with key “upper” specifying the starting position of Upper’s tokens as a list of token descrip- tions (as described below).

• An entry with key “lower” specifying the position of Lower’s tokens as a list of token descriptions.

• An entry with key “block” specifying the position of any blocking tokens as a list of token descriptions.

Each token description is a list of the form [s,r,q] where s is a string representing the token’s symbol (“r” for Rock, “p” for Paper, “s” for Scissors; blocking tokens have no symbol and use the string “”), and (r, q) are the axial coordinates of the token’s hex (see Figure 1).

You may assume that (1) the input matches this format description exactly (we will not give you invalid JSON), (2) all token descriptions contain valid coordinates (we will not give you coordinates outside of the board), (3) there are no overlapping tokens (we will not give you a configuration with two tokens initially on the same hex), and (4) there is at least one winning sequence of actions (we will not give you configurations from which it is impossible to win).

Output format

Your program must print out the actions Upper should take on each turn to win the game. The actions must be printed to standard output4, with one line of output per action, in the following format:

• To output a slide action on turn t for a token on hex (ra,qa) sliding to hex (rb,qb), print the line: ‘Turn t: SLIDE from (ra,qa) to (rb,qb)’.

• To output a swing action on turn t for a token on hex (ra,qa) swinging to hex (rb,qb), print the line: ‘Turn t: SWING from (ra,qa) to (rb,qb)’.

The first turn is numbered 1, and note that in this single-player variant of the game, Upper will take one action with each token on each turn, and these actions happen at the same time. For example, if Upper controls three tokens, the first three lines of output should all begin with ‘Turn 1:’.

The report

Finally, you must briefly discuss your approach to solving this problem in a separate file called report.pdf (to be submitted alongside your program). Your discussion should answer these three questions:

  1. How did you formulate this game as a search problem? Explain your view of the problem in terms of states, actions, goal tests, and path costs, as relevant.
  2. What search algorithm does your program use to solve this problem, and why did you choose this algorithm? Comment on the algorithm’s efficiency, completeness, and optimality. If you have developed heuristics to inform your search, explain them and comment on their admissibility.
  3. How do the features of the starting configuration (the position and number of tokens) impact your program’s time and space requirements? For example, discuss their connection with the branching factor and search tree depth and how these affect the time and space complexity of your algorithm.

Your report can be written using any means but must be submitted as a PDF document. Your report should be between 0.5 and 2 pages in length, and must not be longer than 2 pages (excluding references, if any).