RO_mini-project
Mini-project: tic-tac-toe¶
Copyright By PowCoder代写 加微信 powcoder
#require “fp”
open Project
The aim of this project is to code up a simple game: tic-tac-toe.
Here is a quick demo of the end result, with Blue playing randomly, and Red playing optimally:
let module G = Game (Solutions) in
In this project, you will progressively implement all the functions which are required to make the game work. These functions involve multiple aspects:
basic manipulation of the data structures involved
logic of the various algorithms
The list of all functions you have to implement can be found at the very end of this notebook. But you will be guided throughout the notebook with detailed instructions for each function.
At any point, you can check your solutions by progressively building your own My_solutions module, like so:
module My_solutions : Project.T = struct
(* include the ready-made solutions… *)
include Solutions
(* … and shadows some of the solutions with your own solutions, for example: *)
let other_mark = function
| Blue -> Red
| Red -> Blue
and then test the entire game module, for example by running the following:
let module G = Game (My_solutions) in
let player1 = G.optimal_algorithm Red
and player2 = G.me Blue in
G.game (player2, player1)
Thus, because you have include Solutions in module My_solutions, you will be able to experiment with the game even if you haven’t managed to implement a solution to all functions. In fact, you can also work your way through the various functions in the order that suits you.
You can also test each individual function f by invoking Test.test_f. If your function has the wrong type, the typechecker will complain. If your function has the right type, then a test will be performed and you will be told whether your function “does the right thing”. For example:
Test.test_other_mark My_solutions.other_mark
You should make use of autocompletion to check the expected type and the documentation for each function; in a code cell, documentation pops up when you press Shift+Tab at the end of an expression. If you continue to hold Shift and press Tab once more, the pop up will grow to show the documentation for that function. If you continue to hold Shift and press Tab a third time, that pop up will be sent to the bottom of your browswer and stick there until you decide to close it. Try it! Put your cursor at the end of the word game below and try it:
Solutions.other_mark
Types and data structures¶
The game is structured around a couple of simple types, which have been pre-defined for you in module Project:
(* The two players are characterized by their “color” (Red or Blue): *)
type mark =
(* A 3×3 board configuration is a list of 3 lists (rows),
each with 3 elements.
Each element can be None (empty), or Some mark: *)
type board = mark option list list
(* The game can end in different ways: *)
type outcome =
| Won of mark
(* The result of evaluating a given board:
the game might have finished already,
or it’s unfinished and there is a list of possible next turns.
In principle, Unfinished [] should never occur. *)
type evaluation =
| Finished of outcome
| Unfinished of board list
(* Type for representing the current state of play. *)
type state =
| Playing of board
| Ended of outcome
(* A player owns a mark, and has a strategy for playing.
Playing here means analysing the current state,
and returning a new state. *)
type player =
{ mark : mark
; play : state -> state
List of functions to be implemented¶
Below is a list of all the functions you need to implement in this project. The documentation of each function is available by writing Solutions.name_of_the_function and then pressing Shift+Tab. If you hold Shift and press Tab three times, the documentation pop-up will be moved to the bottom of your window and will stick there until you decide to close it.
#show_module_type Fp__Project.T
Bonus questions¶
Bonus question 1¶
Right now, when it plays against a sub-optimal algorithm, the
optimal algorithm makes seemingly odd choices: when it knows it’s certain to
win in the future, it does not necessarily choose to win quickly. Rather it
lets the opponent die a slow death 🙂 Can you fix this?
Bonus question 2¶
Right now, the algorithm always make the same choices in any configuration,
even though there might be several options with identical values. Introduce
randomness into the algorithm.
Bonus question 3¶
The algorithm we have implemented scales very poorly with the the size of
board: indeed our value function can’t handle a 4×4 board. Do a bit of research
and implement so-called “alpha/beta pruning” to fix this.
Final presentations¶
Each group to give a 20 min presentation
Every member of the group must present a part (everyone must participate)
I am going to assess: quality of the work (correctness of solutions, OCaml writing style, efficiency of code)
quantity (how much have you been able to do, potential Bonus questions)
Q&A (be prepared to answer some of my questions)
clarity of presentation
The presentation has no particular forced structure. Use your own imagination / carefully think through what the best presentation format is, given that you must convey the following:
you need to give me enough information that I can assess the bullet points above
tell me what you have enjoyed, what you have learned from the course
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com