Java代写：COSC2123Battleship

代写Battleship游戏，需要完成三种电脑AI算法：Random, Greedy以及Monte Carlo.

Objectives

There are three key objectives for this project:

• Implement a Battleship game.
• Design and implement Battleship guessing algorithms.
• Have fun!
  This assignment is designed to be completed in groups of 2, or pairs. We
  suggest that you work in pairs, but you may work individually.

Background

Battleship is a classic two player game. The game consists of two players, and
each player has a number of ships and a 2D grid. Player places their ships
onto the grid, and these ships takes up a number of cells. Each player takes
turn at guessing a cell to fire at in their opponent’s grid. If that cell
contains part of a ship, the player gets a hit. If every part of a ship has
been hit, then it is sunk and the owner of the ship will announce the name of
the ship sunk (see ships section below for ships in the standard game). The
aim of the game is to sink all of your opponent’s ships before they sink all
of yours. For more details, see
https://en.wikipedia.org/wiki/Battleship_(game) .
Traditionally, Battleship is played between human players. In this assignment,
your group will develop algorithms to automatically play Battleship, that uses
a variety of the algorithmic paradigms we have covered in class. It will also
give you a taste of artificial intelligence (AI), as algorithms is an
important component of AI.

Ships

In the standard Battleship game, there are five ships available for each side.
They are all rectangular in shape. Their dimensions are as follows:

Name	Dimensions
Destroyer	1 by 2 cells
Cruiser	1 by 3 cells
Submarine	1 by 3 cells
Battleship	1 by 4 cells
Aircraft Carrier	1 by 5 cells

Tasks

The project is broken up into a number of tasks to help you progress. Task A
is to develop a random guessing algorithm as an initial attempt at a
Battleship playing agent. Task B and C develops more sophisticated algorithms
to play Battleship. There is also a bonus task. It is based on extending your
algorithms to a variant of the standard Battleship game. For details on how
each task will be assessed, please see the “Assessment” section.
To help you understand the tasks better, we will use the example illustrated
in Figure 1, which is a Battleship game played on a 10 by 10 grid.

Task A: Implement Random Guessing Player (3 marks)

In this task, your group will implement a random guessing player for
Battleship, which can be considered as a type of brute force algorithm. Each
turn, this type of algorithmic player will randomly select a cell it hasn’t
tried before, fire upon that cell, and continue this process until all the
opponent’s ships are sunk.
As an example, after some rounds, this random guessing player has fired a few
shots and have hit the aircraft carrier (see Figure 2). But its next shot will
still be a random cell that it hasn’t fired upon before (in this example, cell
(3,0), highlighted in red). We can do better then this, which is what the next
type of player is about (task B).

Task B: Implement Greedy Guessing Player (5 marks)

In this task, your group will make two improvements to the random guessing
player. First one is rather than randomly guess, we can utilise the fact that
the ships are at least 2 cells long and use the partiy principle. See Figure
3a. As ships are at least of length 2, the player do not need to fire at every
cell to ensure we eventually find the opponent’s ships. It just need to fire
at every 2nd square (Figure 3a). Hence, when hunting for one of the opponent’s
ships, it can now randonly select a cell from this checkboard type of pattern
The second improvement is to implement more sophicated behaviour once we have
a hit. We now divide the process into two parts: hunting mode, where the
player is seeking opponent’s ships (for this task B type of player, they will
use the parity guessing improvement), and targeting mode, where once there is
a hit, the player greedily tries to sink the partially hit/damaged ship. For
the targeting mode, once a cell register a hit, we know the rest of the ship
must be in one of the four adjacent cells, as highlighted as oranged circles
in Figure 3b. The player seeks to destroy the ship before moving on, hence
will try to fire at those four possible cells first (assuming they haven’t
been fired upon, if they have, then no need to fire at a cell twice). Once all
possible targeting cells have been exhausted, the player can be sure to have
sunk the ship(s) (can be more than one if ships are adjacent to each other)
and it returns to the hunting mode until it finds the next ship.

Task C: Implement Monte Carlo1 Guessing Player (5 marks)

In this task, your group will implement a smarter type of player. This one is
based on the transformand-conquer principle, where we do some preprocessing to
improve our hunting and targeting strategies.
When a ship is sunk, the opponent will indicate which ship of theirs has been
sunk. We can make use of this fact to improve both the hunting and targeting
mode. In the two previous type of players they assumed every cell is as likely
to contain a ship. But this is unlikely to be true. For example, consider the
aircraft carrier and a 10 by 10 grid. It can only be in two placement
configurations if placed in top left corner (see Figure 4a), but in 10
different placement configurations if part of it occupies one of the centre
cell, e.g., cell (4,4) (see Figure 4b). Hence, assuming our opponent randomly
places ships (typically they don’t, but that is beyond this course, as we are
going towards game theory and more advanced AI), it is more likely to find the
aircraft carrier occupying one of the centre cells.
This exercise can be repeated for all ships, and for each ship, we end up with
a count of the number of ship configurations that can occupy that cell. The
cell with the highest total count over all ships is the one most likely to
contain a ship.
In hunt mode, this type of player will select from those cells yet to be fired
upon, the one with the highest possible ship configuration count (if there are
several, randomly select one). If there is a miss, then the count of that cell
and neighbouring cells (because we missed, it means there isn’t any ship that
can occupy that cell, so need to update its count and the neighbouring ones,
as the count of neighbour ones may depend on a ship being upon to fit onto the
fired upon cell). If hit, we go to targeting mode. In targeting more, the
player makes use of the fact that there has been a hit to calculate which
adjacent cell is the most likely to contain a ship (with the highest
configuration count). Using the same counting method as the hunting mode, we
can calculate the number of possible ship configurations that pass through the
hit cell (remember previous misses, previously sunk ships and grid boundaries
should be considered as obstacles and taken into account). When we get a miss
or another hit, update the counts correspondingly and repeat at firing at an
adjacent cell with the highest count. Once a ship is sunk, the counts of the
whole grid must be updated to reflect this ship is no longer in play. When the
player has sunk the ship(s), then it goes back to hunting mode.

Bonus Task: Designing Monte Carlo Player to play in a Hexagonal Grid (3

marks)
Note that the bonus task is deliberately designed to take more time for less
marks than the other tasks. Only attempt this after completing Tasks A-C.
Battleship has been around for decades, and have been played on a rectangular
grid (each cell has 4 sides). In this task, you will extend the Monte Carlo
player of task C to play in a hexagonal grid, where each cell has 6 sides.
Before, ships can only be placed horizontally or vertically, but with a
hexagonal grid, they can also be placed diagonally.

Details for all tasks

To help you get started and to provide a framework for testing, you are
provided with skeleton code that implements some of the mechanics of the game.
The main class (BattleshipMain) implements functionality of a two player
Battleship game, a method to log the game to check the correctness and to
parse parameters. The list of files provided are listed in Table 1.

file	description
BattleshipMain.java	Class implementing basic framework of the Battleship
game. Do not modify unless have to.
player/Player.java	Interface class for a player. Do not modify this file.
player/RandomGuessPlayer.java	Class implementing the random guessing
player (task A).
player/GreedyGuessPlayer.java	Class implementing the greedy guessing
player (task B).
player/MonteCarloGuessPlayer.java	Class implementing the Monte Carlo
guessing player (task C).
player/BonusPlayer.java	Class implementing the bonus task player (bonus
task).
player/Guess.java	Class implementing a ‘guess’. Do not modify this file.
player/Answer.java	Class implementing an ‘answer’. Do not modify this
file.
ship/Ship.java	Interface class for a ship. Do not modify this file.
ship/Destroyer.java	Class implementing a destroyer ship. Do not modify
this file.
ship/Submarine.java	Class implementing a submarine ship. Do not modify
this file.
ship/Cruiser.java	Class implementing a cruiser ship. Do not modify this
file.
ship/Battleship.java	Class implementing a battleship ship. Do not modify
this file.
ship/AircraftCarrier.java	Class implementing an aircraft carrier ship. Do
not modify this file.
world/World.java	Class implementing the “world” of the game for a player,
including the grid, location of their ships and where their opponent have
fired before. It is used for visualisation. If you need to store game
information, we suggest use attributes in the *Player classes. Do not modify
this file.
world/StdDraw.java	Class that implements visualisation. Do not modify this
file.
The framework is designed such that each player can have their own
implementation. This allows your players to play against some of ours, or even
other groups (given certain conditions are satisfied, please ask your lecturer
first). Also, it defines how the players should interact. Examine
BattleshipMain.java, particularly the code that iterates through the rounds.
Note each player takes turn at making a guess via a Guess object, then the
opponent answers via an Answer object and this is passed back to the first
player. Examine the Guess and Answer classes and see “Guess Structure” and
“Answer Structure” below to understand how they are implemented in this
framework.
The framework also automatically logs the guess-answer traces of the game.
This is one mechanism for us to evaluate if your players implementions are
correct (see “Assessment” section for more details).
Note, youo should not modify BattleshipMain class, as this contains the code
for the game mechanics and the logging code and you do not want to break this.
We also strongly suggest to avoid modifying the “Do not modify” ones, as they
form the interface between players and basic ship information. You may add
methods and java files, but it should be within the structure of the skeleton
code, i.e., keep the same directory structure. Similar to assignment 1, this
is to minimise compiling and running issues. However, you can change the
_Player.java files, including implementing/extending from a common player
parent class. However, ultimately your_ Player classes must implement the
Player interface.
Note that the onus is on you to ensure correct compilation on the core
teaching servers.
As a friendly reminder, remember how packages work and IDE like Eclipse will
automatically add the package qualifiers to files created in their
environments.

Guess structure

(row,col) coordinates of the cell fired at.

Answer structure

The answer contains two attributes, isHit and shipSunk. isHit is a boolean,
and should be set to True if a ship was hit by the latest shot, and False if
missed ships. In addition, if a ship is destroyed after the hit, shipSunk
should additionally be set to the object of the ship destroyed, one of
{Destroyer, Cruiser, Submarine, Battleship, AircraftCarrier}.

Compiling and Executing

To compile the files, run the following command from the root directory (the
directory that BattleshipMain.java is in):
javac -cp .:samplePlayer.jar BattleshipMain.java
Note that for Windows machine, remember to replace ‘:’ with ‘;’ in the
classpath.
To run the Battleship framework:
java -cp .:samplePlayer.jar BattleshipMain [-v] [-l ] <ship location file 1> <ship location file 2> <player 1 type> <player 2 type> where

• -v: whether to visualise the game.
• game log file: name of the file to write the log of the game.
• game configuration file: name of the file that contains the configuration of the game.
• ship location file 1: name of file containing the locations of each ship of player 1.
• ship location file 2: name of file containing the locations of each ship of player 2.
• player 1 type: specifies which type of algorithmic player to use for the first player, one of [random | greedy | monte | bonus | sample]. random is the random guessing player, greedy is the greedy guessing player, monte is the Monte Carlo guessing player, bonus is the bonus task player and sample is a sample player we provided for you to initially play with.
• player 2 type: specifies which type of algorithmic player to use for the second player, one of [random | greedy | monte | bonus | sample].
  The jar file contains the sample player to get you going.
  Note: if the game configuration and ship location files are for hex games, the
  framework will automatically switch to a hex world.
  We next describe the contents of the game configuration and chosen person
  files.

Details of Files

Game configuration file

The game configuration files specifies the dimensions of the grid in a Battle
game. The file has the following format:
[# of rows] [# of columns]
The row and column numbers are positive integers, and separated by a space.
An example game configuration file is as follows:
10 20
This specifies the following Battleship game configuration:

• The grid is 10 rows by 20 columns.

Ship location file

The ship location file specifies the location of the ships of each player. It
is formated as follows:
[ ship name ] [ row coordinates ] [ column coordinates ] [ direction the ships spans ]
The values are separated by space.
Ship names are one of {Destroyer, Cruiser, Submarine, Battleship,
AircraftCarrier}. Directions is one of {N (North), S (South), E (East), W
(West)}
An example ship location file is as follows:
Cruiser 1 1 E
Battleship 2 5 S
This specifies the following ship placements:
This can also equally be specified as:
Cruiser 1 3 W
Battleship 5 5 N
As sample, we provide:

• For normal (rectangular) grid world, a “config.txt”, “loc1.txt” and “loc2.txt” as the configuration and ship location files.
• For hexagonal grid world (for bonus task only), a “config_hex.txt”, “loc1_hex.txt” and “loc2_hex.txt” as the configuration and ship location files.

Clarification to Specifications

Please periodically check the assignment FAQ for further clarifications about
specifications. In addition, the lecturer will go through different aspects of
the assignment each week, so even if you cannot make it to the lectures, be
sure to check the course material page on Blackboard to see if there are
additional notes posted.

Assessment

The project will be marked out of 15 (with possible bonus marks of 3).
The assessment in this project will be broken down into a number of
components. The following criteria will be considered when allocating marks.
All evaluation will be done on the core teaching servers.
For all tasks, a cell should not be fired upon more than once. In addition,
answering should be correct, e.g., your implementation should not return False
in Answer.isHit when a ship is actually hit.
If either of these are false, this will be considered as an incorrect
algorithm.

Task A (3/15):

For this task, we will evaluate your player algorithm on whether:

1. It implements a random guessing strategy, as outlined in the specifications.
2. Produces a correct guessing trace, i.e. no cell fired upon more than once, and answering is correct.

Task B (5/15):

For this task, we will evaluate your player algorithm on whether:

1. It implements a greedy guessing strategy, as outlined in the specifications.
2. Produces a correct guessing trace, i.e. no cell fired upon more than once, and answering is correct.
3. Additionally, over a number of games, does it on average, beat the random guessing player of task A, i.e., does it win more than it loses against the random guessing player?

Task C (5/15):

Similar to task B, for this task, we will evaluate your player algorithm on
whether:

1. It implements a Monte-carlo guessing player, as outlined in the specifications.
2. Produces a correct guessing trace, i.e. no cell fired upon more than once, and answering is correct.
3. Additionally, over a number of games, does it on average, beat the player types of task A and B, i.e., does it win more than it loses against each of the other two types of players.

Coding style and Commenting (2/15):

You will be evaluated on your level of commenting, readability and modularity.
This should be at least at the level expected of a second year undergraduate
student who has done some programming courses.

Bonus Task (3/3):

Similar to task C, for this task, we will evaluate your player algorithm on
whether:

1. It implements a Monte-carlo guessing player for hexagonal grids, as outlined in the specifications.
2. Produces a correct guessing trace, i.e. no cell fired upon more than once, and answering is correct.

Late Submissions

Late submissions will incur a deduction of 1.5 marks per day or part of day
late. Please ensure your submission is correct (all files are there, compiles
etc), resubmissions after the due date and time will be considered as late
submissions. The core teaching servers and blackboard can be slow, so please
ensure you have your assignments are done and submitted a little before the
submission deadline to avoid submitting late.

Team Structure

This project is designed to be done in pairs (group of two). If you have
difficulty in finding a partner, post on the discussion forum or contact your
lecturer. If there are issues with work division and workload in your group,
please contact your lecture as soon as possible.

Submission

The final submission will consist of:

• Your Java source code of your implementations. We will provide details closer to submission date.
  Note: submission of the code will be done via Blackboard.

Getting Help

There are multiple venues to get help. There are weekly consultation hours
(see Blackboard for time and location details). In addition, you are
encouraged to discuss any issues you have with your Tutor or Lab Demonstrator.
We will also be posting common questions on Blackboard and we encourage you to
check and participate in the discussion forum on Blackboard. Although we
encourage participation in the forums, please refrain from posting solutions.