博客

CMPT 317

Fall 2020

Introduction to Artifificial Intelligence

理科计算机代写 A collection of Python scripts is posted on the course website. The files contain substantial internal docu-mentation.

Assignment 7

AIMA Chapter 5: Game Tree Search

Date Due: October 30 2020, 11:59pm Total Marks: 14

General Instructions

• This assignment is individual work. You may discuss questions and problems with anyone, but the work you hand in for this assignment must be your own work.

• If you intend to use resources not supplied by the instructor, please request permission prior to starting. You should not use any resource that substantially evades the learning objectives for this assignment. You must provide an attribution for any external resource (library, API, etc) you use. If there’s any doubt, ask! No harm can come from asking, even if the answer is no.

• Each question indicates what the learning objective is, what to hand in, and how you’ll be evalu-ated.
• Do not submit folders, or zip files, even if you think it will help.
• Assignments must be submitted to Moodle.Department of Computer Science

Provided Code  理科计算机代写

For this assignment, you will be exploring the behaviour of game-search algorithms on some dierent games.

A collection of Python scripts is posted on the course website. The files contain substantial internal docu-mentation. The following is a light overview.

• Minimax.py: Depth-Limited Minimax Search (AIMA Chapter 5.2, 5.4)
• AlphaBeta_Full.py: Depth-Limited Minimax Search with Alpha-Beta pruning and Transposition Table  (AIMA Chapter 5.3, 5.4)

• TicTacToe.py: Game Class implementation for the well-known game Tic Tac Toe
• SithVRebels.py: Game Class implementation for the brand new game Sith vs Rebels
• Players.py: Interface class to make it easier to play full games
• compute_firstmove.py: Top-level script to compute the minimax value of the game’s initial state    理科计算机代写
• play_full_games.py: Top-level script to play full games and report a result

You should be able to download and run these scripts “as is”. Make sure they are all in the same directory or project if you are using an IDE.

This may seem like a fair amount of code, here is some advice for dealing with it.

• You probably do not need to even open TicTacToe.py or Players.py at all
• You are encouraged to lightly browse Minimax.py and AlphaBeta_Full.py and compare their dierences,but you will not need to modify either one.

• You will need to make very light modications to compute_firstmove.py and play_full_games.py to gen-erate the data you will need for this assignment. Mostly, this will involve changing the files that are being imported and modifying the lists of depth limits to try
• You will need to have a reasonably good understanding of SithVRebels.py, as you will need to modify it in a non-trivial way

The Sith and the Rebels

The following is the description of a novel game that you will be exploring as part of this assignment.

Consider a 2-person perfect information game played on a N × N chess board, where N is an odd integer greater than 4; i.e., N ∈ {5, 7, 9, 11, · · ·}. The two players are asymmetric:

1. Player One controls the Rebel forces. Initially, there are N Rebels (similar to chess pawns). As described below, a Rebel can be captured by the Sith, or promoted to a Jedi. A Jedi cannot be captured, but can be converted to the Sith forces.

2. Player Two controls the Sith forces. Initially, there is one Sith (similar to a chess King). More Sith can be added to the Sith forces if the Sith converts a Jedi.

The objective of Player One is to capture all the Sith (remove them from the board). The objective of Player Two is to capture or convert all of Player One’s pieces to Player Two pieces (see below).  理科计算机代写

Initial Position The rebels line up on one side of the N × N board. The Sith starts out on the middle column on the other side. Initially, use N = 5. There is an opportunity to experiment with N when everything is working.

Movement and Capture

Rebels move along a single column, one square at a time, always in the forward direction, unless capturing a piece (see below, right). When moving forward into a square, the square must be unoccupied. Unlike pawns in Chess, Rebels do not have the option to move 2 squares when moving from the first row. Rebels capture one square diagonally, in the forward direction (see below, left). If a rebel moves into the last row (the initial row for the Sith), the rebel piece is promoted to a Jedi (similar to a chess Queen). A Jedi can move along any row, column, or diagonal, forward or backward, any number of squares, but cannot jump over other pieces. A Jedi can capture by moving into a square occupied by one of Player Two’s pieces,removing that Sith from the board.

The Sith moves one square in any direction (row, column, diagonal).

If the Sith moves into a square occupied by a Rebel, the Rebel piece is removed. This is a normal capture, as shown below:

However, if the Sith moves into a square occupied by a Jedi, the Jedi is converted, and a new Sith is placed on the board; the new Sith is placed in the square previously occupied by the capturing Sith. (It’s as if the first Sith converts the captured one without moving into the square, because the Jedi becomes a Sith. There is no distinction between Sith pieces. They are all equally powerful and equally valuable.).

In the above diagram, the Jedi was converted, and now there are two Sith.

End of the Game 

Player One wins if all the Sith are captured and removed from the board. Player Two wins if all the Rebel forces are captured or converted. For practical reasons, we put a move limit on the game: if there is no winner by the 40th move (i.e., 20 moves by each player), the game is considered a draw.

In certain situations, a player cannot make a move. For example, if it’s Player 1’s turn to move in the following position, there are no legal moves for the Rebel.

If either player has no legal moves, the game is considered a draw.

Problem Source This game was invented by simplifying the rules of chess, and then a little tinkering with ideas. The game may or may not be any fun for people to play, but it’s good enough as a vehicle to practice the ideas of Chapter 5.

Question 1 (5 points):  理科计算机代写

Purpose: To quantify the eect of alpha-beta pruning and transposition tables on simple games

AIMA Chapter(s): 5.3-5.4

You have been provided with two game-tree search algorithms: basic minimax search, and minimax search with its main standard enhancements: alpha-beta pruning and a transposition table. Both of these algo-rithms are implemented using a depth limit.

For this question, your task is to determine the highest depth limit that can be used for each algorithm such that the program decides on its move in less than 1 second. To do this, use the provided script compute_firstmove.py to build the following table of data, first for the game of Tic Tac Toe.

The size of the table (i.e. the maximum depth limit to try) should be as large as you need it to be in order to answer the question. You can assume that the initial state of the game is the most complex one for the purpose of search, i.e. computing the first move is the most diffcult task for a search algorithm.  理科计算机代写

Then, generate the same table but using Sith vs Rebels as the game instead of Tic Tac Toe.

Once you have your results, in a written document, include your data tables and also answer the following questions:

• What depth limit will you use for Minimax when playing Tic Tac Toe?
• What depth limit will you use for AlphaBeta when playing Tic Tac Toe?
• What depth limit will you use for Minimax when playing Sith vs Rebels?
• What depth limit will you use for AlphaBeta when playing Sith vs Rebels?
• Were your answers to the above questions similar for the two different games or not? Does this result

make sense? Make reference to the rules of the two games and the shape of the resulting search trees in your answer

What to Hand In

Your two data tables and your answers to the five questions in a document called a7q1 with an appropriate extension (e.g., txt, pdf, docx, etc).

Evaluation

• 2 marks: You included data tables for both games with suffcient depth limits to answer the question
• 2 marks: You determined the depth limit to use to keep move times under 1 second for all cases
• 1 mark: Your answer comparing your results for the different games is coherent and shows insight into the search tree structure

Question 2 (4 points):  理科计算机代写

Purpose: To examine the eect of search depth limit on player strength

AIMA Chapter(s): 5.3-5.4

For this question, you will have computer players that use dierent depth limits play against each other at both Tic Tac Toe and Rebels vs Sith and observe the effect of increasing the depth limit on their playing strength (i.e. their ability to win the game). To do this, use the provided script play_full_games.py to generate data for a table in the following format.

In this table, one player should also use a depth limit of M, where M is the depth value you determined that vanilla Minimax search would use to play moves in under 1 second. For the other player, try all depth limits between 1 and A, where A is the depth limit you determined full AlphaBeta search should use in the previous question.

Make one such table for Tic Tac Toe and then again for Rebels vs Sith. Note that both of these games are asymmetric (albeit not to the same degree), which is why you need to swap the depth limits between players in the table for a fair comparison.

Once you have your results, in a written document, include your data tables and also answer the following questions:

• In Tic Tac Toe, does either player have an advantage? Does your answer change if you know either (a) one or both players are weak, or (b) both players are strong?

• In Rebels vs Sith, does either player have an advantage? Does your answer change if you know either (a) one or both players are weak, or (b) both players are strong?

What to Hand In

Your two data tables and your answers to the questions in a document called a7q2 with an appropriate extension (e.g., txt, pdf, docx, etc).

Evaluation

• 2 marks: You included data tables for both games using the depth values you found in the previous question
• 2 marks: Your answer as to which side has an advantage shows insight into both games and the effect of the depth limit

Question 3 (5 points):  理科计算机代写

Purpose: To consider and evaluate the concept of game balance

Highly asymmetric games that are fun and challenging to play can be diffcult to design and often have problems with balance. Generally speaking, for a game to have good balance, the following properties are desirable:

• If both players are of roughly the same skill, either might win (or else a draw is likely, if draws are allowed)

• If one player is more skilled, that player should be able to win playing either side

You may have found from your results that Rebels vs Sith is not at all balanced.

For this question, you will explore the issues of game balance and player strength by proposing and evalfiuating a rules change to Rebels vs Sith. To do this, perform the following three tasks.

Brainstorm

First, brainstorm a list of possible changes you could make to the rules of the game. Be creative, but don’t be TOO ambitious with the scope of your changes: the goal is to balance the existing game, not invent a brand new one. Obvious things to consider might involve changing the number of pieces, changing the initial layout, or changing the movement patterns of certain pieces.

Implement

Choose ONE of the ideas from your brainstorm list and implement it by creating a modied version of RebelsVSith.py. Your idea should be non-trivial (example: simply increasing the dimensions of the board is trivial) but need not be overly complicated. Implementing it will require an understanding of how the existing code stores the game state, generates actions, and applies actions to create new states. Make sure that you test any methods you change very thoroughly, and don’t expect to be able to nd errors merely from the results of re-running search.  理科计算机代写

Evaluate

Test your rules change by generating game play data. Remember that the goal is to evaluate the effect of your change with regard to the desirable properties above. This will require testing with players of dierent skill level. For our purposes, we can simulate skill level by adjusting the depth limit. A player with a higher depth-limit can be considered more skilled.

Although your goal is to select a change that you think will improve balance properties, you will not be graded on whether you actually SUCCEED at improving balance, but only on the correctness of your im-plementation and the rigour of your evaluation.

What to Hand In  理科计算机代写

• A document named a7q3 with an appropriate extension (e.g., txt, pdf, docx, etc) containing:

– A list of all the changes you considered during your brainstorm process. They do not need to be described in detail.

– An indication of the one change you chose to implement and a slightly more detailed description of that change

– A discussion on the implementation of the changes. Summarize WHERE you had to change the code, and what changes you made there.

– Some data (in tabular form) that supports a conclusion.

– A conclusion indicating whether your change succeeded in improving balance    理科计算机代写

• A file named a7q3.py implementing the revised game.

Be sure to include your name, NSID, student number, and course number at the top of all documents.

Evaluation

• 1 marks: You included a list of brainstormed ideas that shows acceptable effort and creativity
• 1 mark: Your summary of your chosen rules change and its implementation description are useful and well-written

• 2 mark: Your rules change is correctly implemented
• 2 mark: Your evaluation is rigorous and supports your conclusion about the success of your change

 

更多代写：行为组织性学代写  雅思代考澳洲  代修夏季网课  北美Reflection essay代写  北美毕业论文代写   澳洲市场营销论文代写

合作平台：essay代写 论文代写 写手招聘 英国留学生代写