代写游戏AI，用MINIMAX和ALPHABETA算法实现最优策略。

Problem Description (Rules of the game)

This game is played by two players, on opposite sides of the game board. The game is played on a board of fixed size 8x8. One player has the Star pieces; the other has the Circle pieces. Player Star plays from the bottom of the board to the top (from A to H) and player Circle plays from the top of the board to the bottom (from H to A). The initial state of the board is shown in the figure below.

Only the dark squares of the board are used. Players alternate turns. When it is a players turn (say player Stars turn), it can do one of the following:

1. Move one of its pieces diagonally to an adjacent unoccupied square on the next row. See figure below.
2. If the adjacent square contains an opponents piece, and the square immediately beyond it (diagonally) is vacant, the opponents piece can be captured (and removed from the game) by jumping over it. See figures below.
3. Pass the move to the other player. A player can only pass if it cannot move any of its pieces.

Note that no backward movement is allowed in this game. According to the description above, any non-pass move in this game is specified by {row letter of initial position}{ column number of initial position}-{row letter of final position}{ column number of final position} of the piece the player chooses to move. For example, C5-D4 describes a move where a piece has been moved from square C5 to square D4. The pass move is denoted by pass.

Last Row Properties

Multiple pieces can be placed on each dark square of the last row (row H for player Star and row A for player Circle), as no valid move is available for pieces located in the last row. See figures below.

Pass Move and End of Game

If one player cannot make a valid move, it must play a pass move, which makes no change on the board, and the game goes to the other players turn. A player cannot pass when it has at least one valid move.

The game ends in two cases:

1. When neither player can make a valid move, the game ends. In other words, when a player plays a pass, and the other player in response also plays a pass, the game ends.
2. When the game reaches a state where only one player has pieces on the board.

Your Task

In this assignment, you will implement the Minimax and Alpha-Beta algorithms to determine the depth-bounded minimax values of given game positions. Your program will take the input from the file input.txt and print out its output to the file output.txt. Each input file contains a game position (including the board state and the player to move), a search cut-off depth D, the values of board rows, and the name of the algorithm to be used (Minimax or Alpha-Beta). Your program should output the corresponding information after running the specified search algorithm to depth D. That is, the leaf nodes of the corresponding game tree should be either a game position after exactly D moves (alternating between Star and Circle) or an end-game position after no more than D moves.

Evaluation function: positional weights

Each square of the board has a certain strategic value, Wi . We assume all squares of a row have the same value. The figure below shows a possible set of values for the rows. Given the weights of the squares, the evaluation function of a given game position, s, (with respect to a specific player) can be computed.

Expansion order and Tie breaking

When it is a players turn (either Star player or Circle player) to play and it has more than one valid move, you must follow this rule for expanding the moves:

First, sort the moves based on the initial position according to the figure below. If two moves have the same initial position, sort them based on the final position according to the figure below. For example, if the valid moves are C3-D4, C3-D2, E5-F4, you should expand them in this order: E5-F4, C3-D2, C3-D4.

Ties between the legal moves are also broken by handling the moves in positional order shown in the figure below (that is, first favor squares in upper rows, and in the same row favor squares in the left side). For example, if a player has the three possible moves C3-D4, C3-D2, and E5-F4, and all of them will end up in the same utility for this player, it should choose E5-F4.

File Formats

Input format:
[PLAYER] which will be either Star or Circle.
[ALGORITHM] which will either be MINIMAX or ALPHABETA and determines the algorithm that you must use to come up with next move
[DEPTH LIMIT] which is a number up to 10 and determines the maximum depth of your minimax or alpha/beta pruning tree
[CURRENT BOARD STATE] contains 8 lines where each line includes 8 square indicators separated by a comma ,. These 8 lines represent the rows of the board from H to A. A square indicator could be S{i}, C{i}, or 0 where {i} indicates the number of pieces (Star or Circle) at that square, and 0 indicates that no pieces are on that square. Note that only squares of row H (for Star) and row A (for Circle) can have more than one Star or Circle piece, respectively. The initial board state will contain at least one piece for each player. Further, the initial board state may not necessarily happen as a result of playing a game from the beginning.
[ROW VALUES] contains one line including 8 increasing numbers separated by a comma ,. This line indicates the values of rows A to H for player Star and the values of rows H to A for player Circle.

Output format:
[NEXT MOVE] the next move played by the player [PLAYER]. Remember that the pass move should be denoted by pass and any non-pass move in this game should be denoted by {row letter of initial position}{ column number of initial position}-{row letter of final position}{ column number of final position} of the piece the player chooses to move. For example, C5-D4 describes a move where a piece has been moved from square C5 to square D4.
[MYOPIC_UTILITY] the instant utility of the player [PLAYER] after playing [NEXT MOVE].
[FARSIGHTED_UTILITY] the utility of the player [PLAYER] at the terminal node of the search tree (considering the maximum depth of [DEPTH LIMIT]) for the game under the assumption that both players select moves maximizing their utilities.
[NUMBER OF NODES] number of nodes visited during the execution of the algorithm [ALGORITHM]. Note that when you implement either MINIMAX or ALPHABETA algorithm, it takes a state as an input. Here, you need to count the number of states (or nodes of the tree) your algorithm visits during the execution.

Note: there should not be any empty new line after [NUMBER OF NODES] line in the output.txt file generated by your code.

Grading

Your homework submission will be tested as follows: Your program should take no command-line arguments. It should read a text file called input.txt in the current directory that contains a problem definition. It should write a file output.txt with your solution. The format for files input.txt and output.txt is specified below. End-of-line convention is Unix (because Vocareum is a Unix system).

During grading, 50 test cases will be used. If your homework submission passes all 50 test cases, you receive 100 points. For each test case that fails, you will lose 2 points.

Note that if your code does not compile, or somehow fails to load and parse input.txt, or writes an incorrectly formatted output.txt, or no output.txt at all, or OuTpUt.TxT, you will get zero points.

Sample Test Cases

You are provided with sample test cases and outputs (see below). The goal of the samples is to help you check if you have correctly parsed the input and generated a correctly formatted output. You should not assume that if your program works on the sample test cases it will work on all test cases.

Example 1

Input:

StarMINIMAX20,S1,0,0,0,0,0,00,0,C1,0,0,0,0,00,0,0,S1,0,0,0,00,0,0,0,0,0,0,00,0,0,0,0,0,0,00,0,0,0,0,0,0,00,0,0,0,0,0,0,00,0,0,0,0,0,0,010,20,30,40,50,60,70,80

Output:

F4-H21601605

Clarification (search tree): In the search tree below, the initial state of the board is denoted by a node named root. The name of a move is denoted beside the arrows, and the name of the node resulting from a move is denoted by that move.

Example 2

Input:

StarALPHABETA20,S1,0,0,0,0,0,00,0,C1,0,0,0,0,00,0,0,S1,0,0,0,00,0,0,0,0,0,0,00,0,0,0,0,0,0,00,0,0,0,0,0,0,00,0,0,0,0,0,0,00,0,0,0,0,0,0,010,20,30,40,50,60,70,80

Output:

F4-H21601604

Clarification (search tree):
Note that Examples 1 and 2 are the same except for their search algorithms which is MINIMAX for the former and ALPHABETA for the latter. Compare these two examples and observe how alpha-beta pruning eliminated one node from the search tree compared to the search tree of Example 1.

Example 3

Input:

StarMINIMAX90,S1,0,0,0,0,0,0S1,0,0,0,0,0,0,00,0,0,0,0,0,0,C10,0,0,0,0,0,0,00,0,0,0,0,0,0,00,0,0,0,0,0,0,00,0,0,0,0,0,0,00,0,0,0,0,0,0,010,20,30,40,50,60,70,80

Output:

G1-H21309026

Example 4

Input:

CircleALPHABETA20,S2,0,0,0,0,0,0S1,0,0,0,0,0,0,00,0,0,0,0,0,0,C10,0,0,0,0,0,S1,00,0,0,0,0,S1,0,00,0,0,0,0,0,0,00,0,0,0,0,0,0,00,0,0,0,0,0,0,010,20,30,40,50,60,70,80

Output:

pass-290-3005

Note that in this case, Circle has no moves available and it has to play pass. Even if it had only one valid move, it had to play that one. Hence, in these cases, doing the search seems unnecessary, but you still need to do the search to calculate [FARSIGHTED_UTILITY], that is, the utility of this player at the terminal node of the search tree.

Example 5

Input

StarALPHABETA70,C1,0,C1,0,C1,0,C1C1,0,C1,0,C1,0,C1,00,S1,0,S1,0,S1,0,S1S1,0,S1,0,S1,0,S1,00,0,0,0,0,0,0,00,0,0,0,0,0,0,00,0,0,0,0,0,0,00,0,0,0,0,0,0,010,20,30,40,52,70,90,1000

Output:

pass3683683

Homework Rules

1. You must use Python 2.7 to implement your homework assignment. You are allowed to use standard libraries only. You have to implement any other functions or methods by yourself.

2. You need to create a file named hw1cs561s2018.py. When you submit the homework on labs.vocareum.com, the following commands will be executed: python hw1cs561s2018.py

3. Your code must create a file named output.txt and print its output there. For each test case, the grading script will put an input.txt file in your work folder, runs your program (which reads input.txt), and check the output.txt file generated by your code. The grading script will replace the files automatically, so you do NOT need to do anything for that part.

4. Homework should be submitted through Vocareum. Homework submitted through email, in person during office hours, or through any channel other than Vocareum will not be accepted. Please only upload your code to the /work directory. Dont create any subfolder or upload any other files.

5. Your program should handle all test cases within a reasonable time. A maximum runtime of 3 minutes per test case will be set on Vocareum.

6. You are strongly recommended to submit at least two hours ahead of the deadline, as the submission system around the deadline might be slow and possibly cause late submission. Late submissions will not be graded.