代写一个棋盘游戏的AI，需要使用Minimax以及Alpha-Beta两种算法。
Guidelines
This is a programming assignment. You will be provided sample inputs and outputs (see below). Please understand that the goal of the samples is to check that you can correctly parse the problem definitions, and generate a correctly formatted output. The samples are very simple and it should not be assumed that if your program works on the samples it will work on all test cases. There will be more complex test cases and it is your task to make sure that your program will work correctly on any valid input. You are encouraged to try your own test cases to check how your program would behave in some complex special case that you might think of. Since each homework is checked via an automated A.I. script, your output should match the example format exactly. Failure to do so will most certainly cost some points. The output format is simple and examples are provided. You should upload and test your code on vocareum.com, and you will submit it there.
Project description
Once upon a time, Los Angeles was a Never Never Land. People were blissfully happy, Conan O’Brien was still on late-night, and no one knew who “the Real Housewives of New Jersey” were. Until the day that two
violent, money-thirsty gangs decided to put their dirty hands onto Los Angeles.
One gang was from the north, and the other gang was from the south. Both wanted to take over the entire city. Therefore, war was unavoidable. To win the war, the leader of the south gang knew that he needed not mere foot troops, but admirals. Therefore, he built an institute to train his future admirals. He named his training institute CSCI-561, and asked his recruits to create artificial agents to engage in a combat simulation, which he called a ‘game’, meant to imitate the upcoming gang war. (Once the members are finished, the leader will classify their research and pull them from the institute, leaving them fractured and bitter human beings. However, as they do not know this yet, they are full of excitement and zeal for the project.)
The game is a simulation of ground warfare and has the following rules:
- The game board is an NxN grid representing the territory your forces will trample (N=5 in the figures below). Columns are named A, B, C, … starting from the left, and rows are named 1, 2, 3, … from top.
- Each player takes turns as in chess or tic-tac-toe. That is, player X takes a move, then player O, then back to player X, and so forth.
- Each square has a fixed point value between 1 and 99, based upon its computed strategic and resource value.
- The object of the game for each player is to score the most points, where score is the sum of all point values of all his or her occupied squares minus the sum of all points in the squares occupied by the other player. Thus, one wants to capture the squares worth the most points while preventing the other player to do so.
- The game ends when all the squares are occupied by the players since no more moves are left.
- Players cannot pass their move, i.e., they must make a valid move if one exists (game is not over).
- Movement and adjacency relations are always vertical and horizontal but never diagonal.
- The values of the squares can be changed for each game, but remain constant within a game.
- Game score is computed as the difference between (a) the sum of the values of all squares occupied by your player and (b) the sum of the values of all squares occupied by the other player. This applies both to terminal (game over, terminal utility function) and non-terminal states (evaluation function). This is required to ensure that your program produces the same results as the grading script.
- On each turn, a player can make one of two moves:
Stake – You can take any open space on the board. This will create a new piece on the board. This move can be made as many times as one wants to during the game, but only once per turn. However, a Stake cannot conquer any pieces. It simply allows one to arbitrarily place a piece anywhere unoccupied on the board. Once you have done a Stake, your turn is complete.
Raid – From any space you occupy on the board, you can take the one next to it (up, down, left, right, but not diagonally) if it is unoccupied. The space you originally held is still occupied. Thus, you get to create a new piece in the raided square. Any enemy touching the square you have taken is conquered and that square is turned to your side (you turn its piece to your side). A Raid can be done even if it will not conquer another piece. Once you have made this move, your turn is over.
Your assignment is
Base homework (required): Create a program to play the game, using, depending on specification in the input file, either the plain Minimax algorithm with depth limit, or Alpha-Beta Pruning.
Competition mode (optional): Your algorithm will play against the other students’ algorithms in a tournament, and the evaluation function is now up to you. You can use any algorithm, heuristic, and trick you wish. Your CPU time will be limited, however. Please see the additional instructions for the competition mode in a separate file.
Pseudo code
To ensure that your outputs will match those of the grading program, please use the following pseudo code to program your algorithm:
Minimax: AIMA Figure 5.3 (Minimax without cut-off) and section 5.4.2 (Explanation of Cutting off search)
Alpha-Beta: AIMA Figure 5.3 (Alpha-Beta without cut-off) and section 5.4.2 (Explanation of Cutting off search)
Example 1
For this input.txt:
3
MINIMAX
O
2
1 8 23
5 42 12
26 30 9
X..
...
...
your output.txt should be:
B3 Stake
X..
...
.O.
Example 2
Using the board state from Figure 3 (left) as the starting configuration for input.txt with minimax search depth = 1,
5
MINIMAX
X
1
20 16 1 32 30
20 12 2 11 8
28 48 9 1 1
20 12 10 6 2
25 30 23 21 10
..XX.
..XOX
...O.
..OO.
.....
The output produced is:
B3 Stake
..XX.
..XOX
.X.O.
..OO.
.....
Which is the correct move given the specified algorithm and search depth, but is not the same move as shown in Figure 3 (right). With search depth of 1, the algorithm just went for the high-value cell in B3.
Example 3
Changing the search parameters so as to use alpha beta pruning with search depth=4 on the otherwise same input.txt as in example 2 results in the following output.txt:
C3 Raid
..XX.
..XOX
..XX.
..XO.
.....
which matches the solution depicted in Figure 3 (right).