Project Specification — proj2
项目规范 — proj2

The objective of this project is to practice and assess your understanding of functional programming and Haskell. You will write code to implement both the guessing and answering parts of a logical guessing game.
该项目的目标是练习和评估您对函数式编程和 Haskell 的理解。您将编写代码来实现逻辑猜谜游戏的猜测和回答部分。

The Game 游戏

Proj2 is a simple two-player logical guessing game created for this project. You will not find any information about the game anywhere else, but it is a simple game and this specification will tell you all you need to know.
Proj2 是为此项目创建的一个简单的两人逻辑猜谜游戏。您在其他地方找不到有关该游戏的任何信息，但这是一个简单的游戏，此规格将告诉您需要了解的所有信息。

The game is somewhat akin to the game of Battleship™, but somewhat simplified. The game is played on a 4×8 grid, and involves one player, the searcher trying to find the locations of three battleships hidden by the other player, the hider. The searcher continues to guess until they find all the hidden ships. Unlike Battleship™, a guess consists of three different locations, and the game continues until the exact locations of the three hidden ships are guessed in a single guess. After each guess, the hider responds with three numbers:
该游戏有点类似于 Battleship™ 游戏，但有所简化。该游戏在 4×8 网格上进行，一名玩家（搜索者）试图找到另一名玩家（隐藏者）隐藏的三艘战舰的位置。搜索者继续猜测，直到找到所有隐藏的船只。与战舰™不同的是，一次猜测由三个不同的位置组成，游戏将继续进行，直到在一次猜测中猜出三艘隐藏船只的确切位置。每次猜测后，隐藏者都会用三个数字进行响应：

1. the number of ships exactly located;
   准确定位的船舶数量；
2. the number of guesses that were exactly one space away from a ship; and
   距离一艘船正好一格的猜测数量；和
3. the number of guesses that were exactly two spaces away from a ship.
   距离一艘船恰好两个空间的猜测数量。

Each guess is only counted as its closest distance to any ship. For example if a guessed location is exactly the location of one ship and is one square away from another, it counts as exactly locating a ship, and not as one away from a ship. The eight squares adjacent to a square, including diagonally adjacent, are counted as distance 1 away. The sixteen squares adjacent to those squares are considered to be distance 2 away, as illustrated in this diagram of distances from the center square:
每次猜测仅计算其与任何船只的最近距离。例如，如果猜测的位置恰好是一艘船的位置，并且与另一艘船相距一平方，则它算作精确定位一艘船，而不是与一艘船相距一平方。与一个方格相邻的八个方格，包括对角相邻的，都算作距离1。与这些方格相邻的 16 个方格被认为相距 2，如距中心方格的距离图所示：

Of course, depending on the location of the center square, some of these locations will actually be outside the board.
当然，根据中心广场的位置，其中一些位置实际上会在棋盘之外。

Note that this feedback does not tell you which of the guessed locations is close to a ship. Your program will have to work that out; that is the challenge of this project.
请注意，此反馈不会告诉您哪个猜测位置靠近船只。你的程序必须解决这个问题；这就是这个项目的挑战。

We use a chess-like notation for describing locations: a letter A–H denoting the column of the guess and a digit 1–4 denoting the row, in that order. The upper left location is A1 and the lower right is H4.
我们使用类似国际象棋的符号来描述位置：字母 A–H 表示猜测的列，数字 1–4 表示行，按此顺序。左上位置是A1，右下位置是H4。

A few caveats:  一些注意事项：

• The three ships will be at three different locations.
  这三艘船将位于三个不同的地点。
• Your guess must consist of exactly three different locations.
  您的猜测必须恰好包含三个不同的位置。
• Your list of locations may be written in any order, but the order is not significant; the guess A3, D1, H1 is exactly the same as H1, A3, D1 or any other permutation.
  您的位置列表可以按任何顺序书写，但顺序并不重要；猜测 A3、D1、H1 与 H1、A3、D1 或任何其他排列完全相同。

Here are some example ship locations, guesses, and the feedback provided by the hider:
以下是一些船舶位置、猜测以及隐藏者提供的反馈的示例：

Here is a graphical depiction of the first example above, where ships are shown as S and guessed locations are shown as G:
以下是上面第一个示例的图形描述，其中船舶显示为 S，猜测位置显示为 G：

The game finishes once the searcher guesses all three ship locations in a single guess (in any order), such as in the last example above. The object of the game for the searcher is to find the target with the fewest possible guesses.
一旦搜索者在一次猜测中（以任何顺序）猜出所有三个船舶位置，游戏就结束了，例如上面的最后一个例子。搜索者游戏的目标是以尽可能少的猜测找到目标。

The Program 该程序

You will write Haskell code to implement both the hider and searcher parts of the game. This will require you to write a function to return your initial guess, and another to use the feedback from the previous guess(es) to determine the next guess. The former function will be called once, and then the latter function will be called repeatedly until it produces the correct guess. You must also implement a function to determine the feedback to give to the searcher, given his guess and a target.
您将编写 Haskell 代码来实现游戏的隐藏器和搜索器部分。这将要求您编写一个函数来返回您的初始猜测，并编写另一个函数来使用先前猜测的反馈来确定下一个猜测。前一个函数将被调用一次，然后后一个函数将被重复调用，直到产生正确的猜测。您还必须实现一个函数，根据搜索者的猜测和目标，确定向搜索者提供的反馈。

You will find it useful to keep information between guesses; since Haskell is a purely functional language, you cannot use a global or static variable to store this. Therefore, your initial guess function must return this game state information, and your next guess function must take the game state as input and return the new game state as output. You may put any information you like in the game state, but you must define a type GameState to hold this information. If you do not need to maintain any game state, you may simply define type GameState = ().
您会发现在猜测之间保留信息很有用；由于 Haskell 是一种纯函数式语言，因此您不能使用全局或静态变量来存储它。因此，您的初始猜测函数必须返回此游戏状态信息，并且您的下一个猜测函数必须将游戏状态作为输入并返回新的游戏状态作为输出。您可以将任何您喜欢的信息放入游戏状态中，但您必须定义一个类型 GameState 来保存此信息。如果你不需要维护任何游戏状态，你可以简单地定义 type GameState = ()。

You must also define a type Location to represent grid locations in the game, and you must represent your guesses as lists of Locations. Your Location type must be an instance of the Eq type class. Of course, two Locations must be considered equal if and only if they are identical. You must also define a function to convert a Location into a two-character string of the upper-case column letter and row numeral, as shown throughout this document.
您还必须定义一个位置类型来表示游戏中的网格位置，并且必须将您的猜测表示为位置列表。您的 Location 类型必须是 Eq 类型类的实例。当然，当且仅当两个位置相同时，才必须将其视为相等。您还必须定义一个函数，将位置转换为由大写列字母和行数字组成的两个字符的字符串，如本文档所示。

What you must define 您必须定义什么

In summary, in addition to defining the GameState and Location types, you must define following functions:
总之，除了定义 GameState 和 Location 类型之外，您还必须定义以下函数：

toLocation :: String → Maybe Location
toLocation :: String → 也许位置

gives Just the Location named by the string, or Nothing if the string is not a valid location name.
仅给出由字符串命名的位置，如果字符串不是有效的位置名称，则返回 Nothing。

fromLocation :: Location → String
fromLocation :: 位置 → 字符串

gives back the two-character string version of the specified location; for any location loc, toLocation (fromLocation loc) should return Just loc.
返回指定位置的两个字符串版本；对于任何位置 loc，toLocation (fromLocation loc) 应该返回 Just loc。

feedback :: [Location] → [Location] → (Int,Int,Int)
反馈 :: [位置] → [位置] → (Int,Int,Int)

takes a target and a guess, respectively, and returns the appropriate feedback, as specified above.
分别采用目标和猜测，并返回适当的反馈，如上所述。

initialGuess :: ([Location],GameState)
初始猜测 :: ([位置],游戏状态)

takes no input arguments, and returns a pair of an initial guess and a game state.
不接受输入参数，并返回一对初始猜测和游戏状态。

nextGuess :: ([Location],GameState) → (Int,Int,Int) → ([Location],GameState)
nextGuess :: ([位置],游戏状态) → (Int,Int,Int) → ([位置],游戏状态)

takes as input a pair of the previous guess and game state, and the feedback to this guess as a triple of the number of correct locations, the number of guesses exactly one square away from a ship, and the number exactly two squares away, and returns a pair of the next guess and new game state.
将之前的猜测和游戏状态作为输入，并将该猜测的反馈作为正确位置数量的三倍，距离船只正好一格的猜测数量，以及距离船只正好两格的猜测数量，以及返回一对下一个猜测和新的游戏状态。

You must call your source file Proj2.hs, and it must have the following module declaration as the first line of code:
您必须调用源文件 Proj2.hs，并且它必须具有以下模块声明作为第一行代码：

  module Proj2 (Location, toLocation, fromLocation, feedback,
                GameState, initialGuess, nextGuess) where

In the interests of simplicity, please put all your code in the single Proj2.hs file.
为了简单起见，请将所有代码放入单个 Proj2.hs 文件中。

Assessment 评估

Your project will be assessed on the following criteria:
您的项目将根据以下标准进行评估：

The correctness of your toLocation, fromLocation, and feedback functions will be assessed through a number of calls to toLocation to construct a target and guess, calls to fromLocation to ensure it returns the correct string, and a number of calls to feedback to see if the correct feedback is produced. The correctness of your guessing code will be assessed based on whether it succeeds in guessing the targets it is given in the available time. Quality will be assessed based on the number of guesses needed to find the given targets. Full marks will be given for an average of 6 guesses per target, with marks falling as the number of guesses rises. Therefore as the number of guesses drops, further small decreases in the number of guesses are increasingly valuable.
您的 toLocation、fromLocation 和反馈函数的正确性将通过多次调用 toLocation 来构建目标和猜测、调用 fromLocation 以确保它返回正确的字符串以及多次调用 Feedback 来查看是否符合要求进行评估。产生正确的反馈。您的猜测代码的正确性将根据它是否在可用时间内成功猜测给定的目标来评估。将根据找到给定目标所需的猜测数量来评估质量。每个目标平均猜测 6 次即可获得满分，随着猜测次数的增加，分数下降。因此，随着猜测数量的下降，猜测数量的进一步小幅减少变得越来越有价值。

Note that timeouts will be imposed on all tests. You will have at least 5 seconds to guess each target, regardless of how many guesses are needed. Executions taking longer than that may be unceremoniously terminated, leading to that test being assessed as failing. Your programs will be compiled with ghc --make before testing, so 5 seconds per test is a very reasonable limit.
请注意，所有测试都会超时。无论需要猜测多少次，您都将有至少 5 秒的时间来猜测每个目标。执行时间超过该时间可能会被毫不客气地终止，从而导致该测试被评估为失败。您的程序将在测试之前使用 ghc --make 进行编译，因此每次测试 5 秒是一个非常合理的限制。

See the Project Coding Guidelines on the LMS for detailed suggestions about coding style. These guidelines will form the basis of the quality assessment of your code and documentation.
有关编码风格的详细建议，请参阅 LMS 上的项目编码指南。这些指南将构成代码和文档质量评估的基础。

Submission 提交

You must submit your code through Grok, similarly to the previous assignment, and like previous exercises. This project will require more code, so you may find the Grok interface less convenient than your usual preferred editor. Feel free to use whatever tools you like to develop the code, but when you are finished, you must copy your code into the Grok window. Make sure you hit the Mark button to submit your code once it’s ready.
您必须通过 Grok 提交代码，类似于之前的作业以及之前的练习。该项目将需要更多代码，因此您可能会发现 Grok 界面不如您常用的首选编辑器方便。您可以随意使用您喜欢的任何工具来开发代码，但是完成后，您必须将代码复制到 Grok 窗口中。确保在代码准备好后点击“标记”按钮提交代码。

You may submit your code as often as you like, with no penalty for repeated submissions.
您可以根据需要多次提交代码，重复提交不会受到处罚。

Testing your code 测试你的代码

The Compile button in Grok will not work for this project, because it is intended to be used to compile a full Haskell program with a main function. You’ll want to test your code either on your own computer using ghci, or in Grok by using the Terminal button. Normally once you click Terminal in Grok, you’ll automatically have access to the functions you’ve defined and be able to test them, however since your code file for this project is Proj2.hs, Grok doesn’t automatically load the file for you. You can load the file in Grok using the following ghci command:
Grok 中的“编译”按钮不适用于该项目，因为它旨在用于编译带有 main 函数的完整 Haskell 程序。您需要使用 ghci 在自己的计算机上测试代码，或者使用终端按钮在 Grok 中测试代码。通常，一旦您在 Grok 中单击“终端”，您将自动访问您定义的函数并能够测试它们，但是由于该项目的代码文件是 Proj2.hs，Grok 不会自动加载该文件你。您可以使用以下 ghci 命令在 Grok 中加载该文件：

(actually, you can abbreviate that to :l Proj2 and you can get help on the valid ghci commands with the :help command). This is how you must use ghci when it is installed on your own computer, as well.
（实际上，您可以将其缩写为 :l Proj2，并且可以使用 :help 命令获取有关有效 ghci 命令的帮助）。这也是当 ghci 安装在您自己的计算机上时必须使用的方式。

When you are ready to submit your code through Grok, hit the Mark button. This will perform a few tests and show you the feedback. But for this project, it will only run some sanity checks. Passing these sanity checks does not guarantee that your code will pass all tests. You must thoroughly test your own code.
当您准备好通过 Grok 提交代码时，请点击“标记”按钮。这将执行一些测试并向您显示反馈。但对于这个项目，它只会运行一些健全性检查。通过这些健全性检查并不能保证您的代码将通过所有测试。您必须彻底测试您自己的代码。

The first sanity check will check the correctness of your feedback function. Following checks will check your guessing code (yourinitialGuess and nextGuess functions) with decreasing limits on the number of guesses. If your code passes all of these checks (with no failed checks), it is likely your code will achieve a fairly low average number of guesses when the final testing is performed (so it is likely to receive most of the points for average number of guesses). If your code fails a sanity check, you should check the message to determine the cause. It may simply be that your code took too many guesses for a particular test case; that does not mean you code is wrong, just that it may not receive a high mark for the quality of its guessing.
第一次健全性检查将检查您的反馈功能的正确性。以下检查将检查您的猜测代码（yourinitialGuess 和 nextGuess 函数），并减少猜测次数的限制。如果您的代码通过了所有这些检查（没有失败的检查），那么在执行最终测试时，您的代码很可能会获得相当低的平均猜测数（因此它可能会获得平均猜测数的大部分分数）。猜测）。如果您的代码未通过健全性检查，您应该检查消息以确定原因。可能只是因为您的代码对特定测试用例进行了太多猜测；这并不意味着您的代码是错误的，只是它的猜测质量可能不会得到高分。

Late Penalties 逾期处罚

Late submissions will incur a penalty of 0.5% of the possible value of that submission per hour late, including evening and weekend hours. Late submissions will incur a penalty of 0.5% per hour late, including evening and weekend hours. This means that a perfect project that is much more than 4 days late will receive less than half the marks for the project. If you have a medical or similar compelling reason for being late, you should contact the lecturer as early as possible to ask for an extension (preferably before the due date).
逾期提交将受到每小时提交可能价值 0.5% 的处罚，包括晚间和周末时间。逾期提交将受到每小时 0.5% 的罚款，包括晚上和周末时间。这意味着，一个完美的项目如果迟到 4 天以上，所获得的分数将不到该项目的一半。如果您有医疗原因或类似的令人信服的迟到原因，您应该尽早联系讲师以请求延期（最好在截止日期之前）。

Hints 提示

1. Start by defining your Location type. Take care to design an appropriate type. Then write your toLocation and fromLocation functions to convert between a a Location to a two-character String.
   首先定义您的位置类型。注意设计合适的类型。然后编写 toLocation 和 fromLocation 函数以将位置转换为两个字符的字符串。

   Next write your feedback function and test it very carefully. If your feedback function is erroneous, correct guessing code can easily go wrong.
   接下来编写您的反馈函数并仔细测试它。如果你的反馈函数是错误的，正确的猜测代码很容易出错。

   Finally, write your initialGuess and nextGuess functions. I suggest starting with a simple implementation, and get it working, before trying to reduce the number of guesses. Below are several hints for that.
   最后，编写您的initialGuess 和nextGuess 函数。我建议从一个简单的实现开始，并让它发挥作用，然后再尝试减少猜测的数量。以下是一些提示。

2. A very simple approach to this program is to simply guess every possible combination of locations until you guess right. There are only 4960 possible targets, so on average it should only take about 2480 guesses, making it perfectly feasible to do in 5 seconds. However, this will give a very poor score for guess quality.
   该程序的一个非常简单的方法是简单地猜测每个可能的位置组合，直到猜对为止。可能的目标只有 4960 个，因此平均只需要大约 2480 次猜测，这使得在 5 秒内完成是完全可行的。然而，这会给猜测质量带来非常差的分数。
3. A better approach would be to only make guesses that are consistent with the answers you have received for previous guesses. You can do this by computing the list of possible targets, and removing elements that are inconsistent with any answers you have received to previous guesses. A possible target is inconsistent with an answer you have received for a previous guess if the answer you would receive for that guess and that (possible) target is different from the answer you actually received for that guess.
   更好的方法是只做出与您之前收到的猜测答案一致的猜测。您可以通过计算可能目标的列表并删除与您之前收到的猜测答案不一致的元素来做到这一点。如果您收到的该猜测的答案和该（可能的）目标与您实际收到的该猜测的答案不同，则可能的目标与您收到的先前猜测的答案不一致。

   You can use your GameState type to store your previous guesses and the corresponding answers. Or, more efficient and just as easy, store the list of remaining possible targets in your GameState, and pare it down each time you receive feedback for a guess. That way you don’t need to remember past guesses or feedback.
   您可以使用 GameState 类型来存储您之前的猜测和相应的答案。或者，更高效、更简单的方法是，将剩余可能目标的列表存储在 GameState 中，并在每次收到猜测反馈时将其缩减。这样你就不需要记住过去的猜测或反馈。

4. The best results can be had by carefully choosing each guess so that it is most likely to leave a small remaining list of possible targets. You can do this by computing for each remaining possible target the average number of possible targets that will remain after each guess, giving the expected number of remaining possible targets for each guess, and choose the guess with the smallest expected number of remaining possible targets.
   通过仔细选择每个猜测，以便最有可能留下一小部分可能目标，可以获得最佳结果。为此，您可以为每个剩余的可能目标计算每次猜测后剩余的可能目标的平均数量，给出每个猜测的剩余可能目标的预期数量，并选择剩余可能目标的预期数量最小的猜测。
5. Unfortunately, this is much more expensive to compute, and you will need to be careful to make it efficient enough to use. One thing you can do to speed it up is to laboriously (somehow) find the best first guess and hard code that into your program. After the first guess, there are much fewer possible targets remaining, and your implementation may be fast enough then.
   不幸的是，这的计算成本要高得多，并且您需要小心以使其足够高效以供使用。为了加快速度，您可以做的一件事是费力地（以某种方式）找到最佳的第一猜测并将其硬编码到您的程序中。在第一次猜测之后，剩下的可能目标就会少得多，那么你的实现可能就足够快了。

   The choice of a good first guess is quite important, and the best first guess might not be what you’d intuitively expect. It turns out you get more information from feedback like (0,0,0) (which tells you there are no ships within 2 spaces of any of the guessed locations) than from feedback like (1,1,1), which says there are ships near all your guesses, but not where they are.
   选择一个好的初步猜测非常重要，而最好的初步猜测可能不是您直观地期望的。事实证明，您从 (0,0,0)（它告诉您任何猜测位置的 2 个空间内没有船只）这样的反馈中获得的信息比从 (1,1,1) 这样的反馈中获得的信息更多，后者表示有船只是否接近您的所有猜测，但不是它们所在的位置。

6. You can also remove symmetry in the problem space. The key insight needed for this is that given any guess and an answer returned for it, the set of remaining possibilities after receiving that answer for that guess will be the same regardless of which target yielded that answer. In other words, all the guesses that yield the same feedback will leave you with the same set of remaining possibilities — specifically, the set of guesses that yield that feedback.
   您还可以消除问题空间中的对称性。为此所需的关键见解是，给定任何猜测和为其返回的答案，在收到该猜测的答案后剩余的可能性集将是相同的，无论哪个目标产生了该答案。换句话说，产生相同反馈的所有猜测都会给你留下相同的剩余可能性集——具体来说，产生该反馈的猜测集。

   For example, suppose there are ten remaining candidate targets, and one guess gives the answer (3,0,0), three others give (1,0,2), and the remaining six give the answer (2,0,1). In this case, if you make that guess, there is a 1 in 10 chance of that being the right answer (so you are left with that as the only remaining candidate), 3 in 10 of being left with three candidates, and a 6 in 10 chance of being left with six candidates. This means on average you would expect this answer to leave you with
   例如，假设剩下十个候选目标，其中一个猜测给出答案（3,0,0），另外三个给出（1,0,2），剩下的六个给出答案（2,0,1） 。在这种情况下，如果您做出这样的猜测，则有十分之一的机会是正确答案（因此您将成为唯一剩下的候选者），十分之三的机会将留下三个候选者，而 6剩下 6 名候选人的机会为 10 分。这意味着平均而言您会期望这个答案给您留下$$\frac{1}{10}\times 1+\frac{3}{10}\times 3+\frac{6}{10}\times 6=4.6$$ remaining candidates. In general, the formula is:
   剩余候选人。一般来说，公式是：$$\sum _{f\in F}\frac{count(f{)}^2}{T}$$ where F is the set of all distinct feedbacks ((3,0,0), (1,0,2), and (2,0,1) in the example above), count(f) is the number of occurrences of the feedback f (1 for (3,0,0), 3 for (1,0,2), and 6 for (2,0,1) in the example), and T is the total number of tests (10 in the example).
   其中 F 是所有不同反馈的集合（上例中的 (3,0,0)、(1,0,2) 和 (2,0,1)），count(f) 是出现的次数反馈 f（在示例中，(3,0,0) 为 1，(1,0,2) 为 3，(2,0,1) 为 6），T 是测试总数（在示例中为 10）这个例子）。

   Once you’ve computed this for each possible guess, you can just pick one that gives the minimum expected number of remaining candidates.
   一旦你计算出每个可能的猜测，你就可以选择一个给出剩余候选者的最小预期数量的猜测。

   Also note that if you do this incorrectly, the worst consequence is that your program takes more guesses than necessary to find the target. As long as you only ever guess a possible target, every guess other than the right one removes at least one possible target, so you will eventually guess the right target.
   另请注意，如果您这样做不正确，最糟糕的后果是您的程序需要更多的猜测来找到目标。只要你只猜测一个可能的目标，除了正确的目标之外的每一次猜测都会删除至少一个可能的目标，所以你最终会猜测正确的目标。

7. Note that these are just hints; you are welcome to use any approach you like to solve this, as long as it is correct and runs within the allowed time.
   请注意，这些只是提示；欢迎您使用任何您喜欢的方法来解决此问题，只要它是正确的并且在允许的时间内运行即可。

Note Well: 请注意：

This project is part of your final assessment, so cheating is not acceptable. Any form of material exchange between teams, whether written, electronic or any other medium, is considered cheating, and so is the soliciting of help from electronic newsgroups. Providing undue assistance is considered as serious as receiving it, and in the case of similarities that indicate exchange of more than basic ideas, formal disciplinary action will be taken for all involved parties. If you have questions regarding these rules, please ask the lecturer.
该项目是您最终评估的一部分，因此作弊是不可接受的。团队之间任何形式的材料交换，无论是书面的、电子的还是任何其他媒介，都被视为作弊，向电子新闻组寻求帮助也被视为作弊。提供不正当援助与接受援助一样严重，如果存在相似之处，表明交换的不仅仅是基本想法，将对所有相关方采取正式的纪律处分。如果您对这些规则有疑问，请询问讲师。