首页 » Python辅导 » Python辅导 | CMPT310 Summer 2019 Assignment 4

Python辅导 | CMPT310 Summer 2019 Assignment 4

Python实现蒙特卡罗树搜索要求使用A*图算法

Assignment 4

As explained below, this assignment requires that you submit two files on Canvas:

  • a4.py, which has your implementation of part 1
  • project_info.txt, which has information about your project choice for assignment 5

Part 2: Project Preparation

Assignment 5 is a project that you can work on either by yourself, or with a partner (teams larger than 2 are not permitted).

So, in a file named project_info.txt, tell us this information:

  • The name of everyone on your team. Teams may have 1 or 2 people (teams of more than 3 are strictly not allowed).

    If you are on a team of 2, you will need to talk to a TA about signing up in a team on Canvas.

    Please note that we will expect a little more work from teams of 2, and we expect both members to do an equal amount of work. Teams of 2 that don’t follow these rules may have their marks adjusted appropriately.

  • The project (see below) that you’ve chosen to work on.

  • The main programming language you plan to use, plus a list of any libraries you plan to use.

    Please note that general-purpose helper libraries of code are permitted, but no libraries that implement key AI techniques are permitted: the purpose of this assignment is for you to implement some AI algorithms on your own, and so calling existing versions of the algorithms is not what we want to see.

Project: The 15-puzzle and Pattern Databases

Implement a program that can optimally solve random instances of the 15-puzzle (and also the 25-puzzle, if you can).

The markers will be looking for the following:

  • Use of a memory-efficient A* algorithm, such as IDA*.
  • Use of an efficient programming language, such as C++ (Python is probably not efficient enough).
  • Creation and use of pattern databases to be used as admissible heuristics.
  • Speedy solving times: people have reported being able to optimally solve random instances of the 15-puzzle in around 1 second using admissible heuristics based on pattern databases.
  • A written report of at least one page that explains your program, the techniques it uses, its results, etc. This should include graphs and tables of relevant data.

Project: Fast Implementations of WalkSAT and Resolution Proving

Implement an efficient version of both WalkSAT, and a propositional theorem prover based on resolution. They should both use the minisat input format. Using the same set of test examples, compare the performance of your two algorithms against the Python version of WalkSAT (in the textbook code in logic.py) and minisat. Use randomly generated k-CNF sentences as input (these are described in the textbook in the first full paragraph of page 264).

The markers will be looking for the following:

  • Implementation of WalkSAT using an efficient programming language, such as C++ (Python is probably not efficient enough).
  • Implementation of a propositional theorem prover based on resolution using an efficient programming language, such as C++ (Python is probably not efficient enough).
  • Speedy solving times: not only should you use an efficient programming language, but you should use efficient data structures and algorithms, plus anything else you can imagine to make this run efficiently.
  • Randomly generated k-sat expressions. Note that this part of your project could probably be done in Python, as efficiency is not as important as it is for the main solvers.
  • A written report of at least one page that explains your programs, the techniques they use, the results of your comparisons, etc. This should include graphs and tables of relevant data.

Project: Peaceable Queens

As explained in this video, the peaceable queens problem asks how many black and white queens can be placed on an n-by-n chess board so that there are an equal number of white queens and black queens, and no two queens of different colors attack each other.

Information about current results can be found here: https://oeis.org/A250000. For example, since the video was published, apparently the value for n=15 has been found to be 32. Starting at n=1, here is the currently known sequence of values:

0, 0, 1, 2, 4, 5, 7, 9, 12, 14, 17, 21, 24, 28, 32

Solve this problem in at least two different ways: using minisat, and using min-conflicts customized for peaceable queens. The min-conflicts approach is intriguing because customized version of min-conflicts can efficiently find solutions to the regular n-queens problem for n in the millions in less than a minute.

The markers will be looking for the following:

  • A CNF encoding of the peaceable queens problem for any board size n > 1.

    The details of how to do this are up to you: try to work it out from first principles.

  • An implementation of a customized min-conflicts style algorithm. Efficiency is important, so you should do this in a language more efficient than Python (e.g. C++).

    The exact details of the algorithm are up to you: experiment, and try out some different ideas.

    Note that there is no guarantee that a min-conflicts style algorithm will work as well for this problem as it does for the regular n-Queens!

  • For n=1 up to n=15 (or as big a value of n your program can handle) as you can handle, verify the values given in the video and listed at https://oeis.org/A250000.

  • Make an attempt find the solution for n=16 (or higher). If you think you’ve proven a value for n=16 (or higher), let us (and others!) know!

  • A written report of at least one page that explains your CNF encoding, the techniques in your min-conflicts style algorithm, the results of your programs, etc. This should include graphs and tables of relevant data.

Project: Connect 4 or Reversi

Re-do part 1 of this assignment, but instead of Tic Tac Toe use either the game Connect 4 (on a board with 7 columns and 6 row), or Reversi (on an 8-by-8 board).

It may be harder to make perfect players for these games, but make them play as well as you can.

The markers will be looking for the following:

  • Use of a language more efficient than Python. Doing lots of random playouts as quickly as possible is the key to success. You should keep an estimate of how many playouts per second your program can do as a measure of its performance.

  • You program should play as well as possible, although perhaps not perfectly. Note that it has been proven that the first player can always force a win in Connect 4.

    So that games don’t go on too long, you should put a limit on the maximum amount of time the computer can use (e.g. 5 seconds at most per move).

  • In addition to the pure Monte Carlo Tree Search version of your program, created a second modified version of your program that uses heuristics — and any other additions you think would help — to make (hopefully) better-than-random moves during the playouts.

    Make this version of your program play against the other version to see which one is better.

  • A written report of at least one page that explains your implementations, discusses how well they play, the extra techniques used by your second version, a comparison of which program is stronger, etc. This should include graphs and tables of relevant data.


程序辅导定制C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB


本网站支持 Alipay WeChatPay PayPal等支付方式

E-mail: vipdue@outlook.com  微信号:vipnxx


如果您使用手机请先保存二维码,微信识别。如果用电脑,直接掏出手机果断扫描。

blank

发表评论

您的电子邮箱地址不会被公开。