关于jquery:CAB402-Programming

74次阅读

共计 24526 个字符,预计需要花费 62 分钟才能阅读完成。

CAB402 Programming Paradigms
Assignment 1
Due: 18th April 2019
Worth: 30%
The purpose of this assignment is to develop your functional programming skills by developing a non-trivial application using F#.
The principal focus will be on learning to program in a“pure”functional style – i.e. without making use of any mutable state. In
order to contrast this pure functional style of programming with the more traditional imperative (impure) and object-oriented
paradigms, you will develop three separate implementations of the same software component:

  1. A pure functional implementation using F#
  2. An impure F# implementation that uses mutable state to improve performance
  3. An object-oriented C# implementation
    Game Theory
    Computers can now play many games (such as chess) better than even the best human players. They do so using a branch of
    Artificial Intelligence called Game Theory (https://en.wikipedia.org/wiki… Game Theory has also been used in more
    serious domains to help make optimal business and military decisions. Game Theory is most commonly applied in so called“zerosum”
    games, i.e. for games in which you are competing against an opponent and a potential move that is“good”from your
    perspective is“bad”from their perspective and vice versa. In other words there are no“win-win”scenarios.
    Minimax Algorithm
    The basic algorithm used for determining the optimal move in such zero-sum games is called Minimax. It involves exploring a
    search tree that enumerates all possible moves you could make, and for each of those, all possible moves that your opponent
    could make, and for each of those, all possible moves you could then make and so on. For simple games like Tic-Tac-Toe it is
    possible to consider all possible combinations of moves all the way to the end of the game, where either one player has won or it
    is a draw. These ended games becomes the leaf nodes of the search tree. It is easy to assign a score to these leaf nodes, we simply
    assign a score of +1 if we win, -1 if we lose or 0 if it is a draw. We then use these leaf node scores to assign a score to the nodes
    higher in the search tree. If we are at odd level of the search tree that corresponds to where we get to choose our move then
    clearly we want to select the move that is best from our perspective, so we choose the branch leading to the child node that has
    the highest score and assign that highest score as the computed score for this parent node. Similarly, if we are at an even level in
    the search tree that corresponds to where our opponent gets to choose their move then we assume that they will play
    intelligently/optimally and choose a move/branch that is best for them, which is the one that will be worst from our perspective.
    So, at the even levels we are choosing the maximum score, while at the odd levels we are choosing the minimum score – hence
    the name Minimax (https://en.wikipedia.org/wiki… See Figure 1 for an example of how scores are computed in a bottom
    up fashion based on the given leaf node scores.
    Figure 1 https://en.wikipedia.org/wiki…
    Heuristic Scores
    In simple games like Tic-Tac-Toe we are able to explore all possible combinations of moves all the way to the end of the game –
    so we are guaranteed to always play optimally and never lose. In more complex games such as chess there are too many possible
    combinations of moves to explore all the way to the end of the game. We can still apply the same basic process of building a
    Minimax search tree, however rather than extending all the way to the end of the game, we just stop after some fixed number of
    levels. The leaf nodes in this search tree do not necessarily correspond to the end of the game, so it is not always possible to
    compute a score that perfectly captures which game situation is best. We instead use a heuristic score that aims to approximately
    capture how good a given game situation is from the perspective of one of the players. In chess for example, we would typically
    assign a different weight to each of the pieces we have remaining, for example a queen might be worth 1000 points, while a Knight
    is only worth 350 points (https://www.chessprogramming…. More sophisticated scoring functions would take into
    account not just the pieces that each player has, but how they are arranged in terms of controlling various regions of the board.
    Tic-Tac-Toe
    In this assignment, we will apply the Minimax algorithm to the simple game of Tic-Tac-Toe (https://en.wikipedia.org/wiki…
    where it is possible to consider all possible combinations of moves to the end of the game, so we do not need to worry about
    setting a maximum search depth and our heuristic scoring function will give us a perfect evaluation for the leaf nodes.
    Skeleton Solution
    You have been provided with a skeleton solution that you are required to use. It consists of one Visual Studio Solution that contains
    nine (9)separate Visual Studio projects. The first Visual Studio project is for an F# class library called GameTheory. The GameTheory
    project contains an F# file called GameTheory.fs that contains a function called MiniMaxGenerator. Your first task it to complete
    the implementation of this function using a pure functional style – i.e. without making use of any mutable state. This function is
    designed to be generic, to work for all possible zero-sum games (e.g. Chess), not just Tic-Tac-Toe. MinimaxGenerator in
    GameTheory is a higher-order function, it takes functions as inputs and produces a Minimax function as its output. The functions
    provided as input are used to compute:
    a heuristic score for any game situation,
    determine which player’s turn it is in a given game situation,
    whether a game is over,
    enumerate all possible moves from a given game situation
    apply a move to a game situation to create a new game situation
    The system is kept pure by never changing a game state. We instead have an applyMove function which creates a new game state
    based on a previous game state and a particular move. The previous game state does not change, it just gives rise to a new
    (separate) game state. This approach is central to functional programming.
    The Minimax function that is returned is of type: (‘Game->’Player->Option<‘Move>*int), i.e. a function that takes a current
    game state and a player (from who’s perspective we are choosing the best move) and returns a tuple containing the best move (if
    one exists) and the score associated with this game state. If we are at the end of the game then the best move will be None as
    there are no further legal moves possible once the game is over.
    Unit Tests
    To help you test if your MiniMaxGenerator function has been implemented correctly we have provided you with some unit tests
    in one of the Visual Studio Projects called GameTheoryTests. In order to run these tests within Visual Studio just build the solution,
    open the“Test Explorer”window (Test Menu/Windows/Test Explorer) and run the GameTheoryTests. These tests are based
    on the search tree in Figure 1.
    Alpha-Beta Pruning
    The problem with MiniMax is that it explores an exponential number of search tree nodes (if at each game situation there are m
    possible moves then a search tree of depth n will contains mn nodes). However, if we are clever we can avoid exploring many of
    these nodes while never missing the best possible move. The trick is to introduce two new parameters alpha and beta to our
    recursive MiniMax function (https://en.wikipedia.org/wiki… The parameter alpha is used to keep track of the
    lowest possible score that this node might be given and the parameter beta is used to keep track of the highest possible score
    that this node might be given. If we are applying alpha-beta pruning to a Tic-Tac-Toe game where the heuristic score function will
    always return +1, -1 or 0, so the initial call to Minimax will give alpha a value of -1 and beta a value of +1. However, as we make
    recursive calls and get deeper into the search tree, the lower bound alpha and the upper bound beta become closer together. For
    example if we are at a level in the tree where we are maximizing and come across a move with a score s greater than the lower
    bound alpha, then s will become the new alpha lower bound. Similarly if we are minimizing and come across a move with a score
    t less than the upper bound beta, then t will become the new upper bound beta. If at any stage beta becomes less than or equal
    to alpha then we can stop searching the remainder of the child branches as we have already determined the best possible move
    from that node. In this way we can prune away significant segments of the search tree without giving up on finding the optimal
    move. See Figure 2 for an example of how alpha beta pruning allows us to avoid exploring the nodes marked gray. For Tic-ToeToe,
    rather than searching 526,906 nodes using basic MiniMax, we instead need to explore only 16,087 nodes – resulting in a
    massive time saving.
    Figure 2: Alpha Beta Pruning
    Your second task is to implement the MiniMaxWithAlphaBetaPruningGenerator function in a pure functional style.
    [Tip: this is actually one of the more complex tasks in the assignment – so you may wish to defer it until you have completed some
    of the simpler tasks that follow].
    Tic-Tac-Toe Model
    Next we will use these generic Game Theory functions to help implement a Tic-Tac-Toe game. A classic Tic-Tac-Toe game is played
    on a 3 x 3 grid, but we generalize the game slightly to allow it to be played on a grid of size N x N (where N is called the“size”of
    the game). To win the game, a player must complete an entire straight line of N squares. The line can be one of N possible rows,
    N possible columns or 2 possible diagonals. Your code, therefore should not contain the magic number 3 – everything should be
    based on the more general case of an N x N board.
    In the FSharpTicTacToeModel project you will find an F# file TicTacToePure.fs that contains skeleton implementations for many
    of the Tic-Tac-Toe related functions that you will need to pass to the Minimax function in the Game Theory library. The
    FSharpPureTicTacModel module also contains functions Minimax and MinimaxWithPruning that you will implement by calling
    the MiniMaxGenerator and MiniMaxiWithAlphaBetaPruningGenerator functions from the GameTheory library. Before you
    implement those functions you will need to first design the F# data structures that you will use to represent the state of a Tic-TacToe
    game, a Tic-Tac-Toe move and a Tic-Tac-Tac player. The Tic-Tac-Toe game state includes not just the state of the board (and
    its size), but also which player’s turn it is. The Tic-Tac-Toe moves are represented via the (row, column) coordinates of each square,
    with the top left square having coordinates (0, 0). In Tic-Tac-Toe the two players are Nought and Cross.
    TicTacToePure.fs also contains a helper function called GameOutcome that you must implement. It takes a game as input and
    returns a TicTacToeOutcome as defined in the TicTacToeInterfaces project. TicTacToeOutcome is an F# discriminated union
    type designed to convey the outcome of the game. If one of the players has won then the outcome will be Win with the winner
    field set to the player who won and the line field telling us the coordinates of the squares corresponding to the winning line (row,
    column or diagonal). If neither player has won then the outcome will be either Draw or Undecided. The game should be considered
    a draw if every possible line (row, column or diagonal) contains both a Cross and a Nought. The GameOutcome function should be
    used to help implement both the GameOver function and the HeuristicScore function. The GameOutcome function should be
    implemented with the help of the Lines function and the CheckLine functions. The Lines function returns a sequence containing
    all of the lines on the board: horizontal, vertical and diagonal. The CheckLine function takes as input both a game and a single line
    and tells us (based on considering just that one line alone) if the game has been won, drawn or undecided. Other helper functions
    should also be created as needed.
    Everything in the TicTacToePure.fs must be implemented in a pure functional style, i.e. without using any mutable state.
    The TicTacToeModelTests project contains unit tests that you can use to help test your code.
    MVVM (Model-View-ViewModel)
    So far we have implemented just the basic functions needed for a game of Tic-Tac-Toe. Those functions need to be incorporated
    into a GUI app that will actually play a game of Tic-Tac-Toe against a human opponent. The GUI app will use the Model-ViewViewModel
    (MVVM) architectural pattern. See:
    https://en.wikipedia.org/wiki…,
    https://docs.microsoft.com/en…,
    https://docs.microsoft.com/en…,
    https://blogs.msdn.microsoft….
    The GUI app is split into 3 components: The Model, The View and the ViewModel. The model provides data structures for
    representing objects in the domain as well as basic“business logic”for the application domain. In our case, the application domain
    is Tic-Tac-Toe, so the F# component that we have implemented so far will be used as the Model in our MVVM application. The
    View is the part of the application that determines what the user sees on the screen and what user interactions (clicks, keyboard,
    gestures, etc) are allowed. The ViewModel acts as a bridge between the View and the Model:
    https://documentation.devexpr…
    The ViewModel provides an abstract view of the User Interface, it exposes information via properties that should be presented
    to the user (somehow) and commands which are the different abstracted operations that the user might trigger via the user
    interface (somehow). For example, our Tic-Tac-Toe ViewModel exposes a property called Message that is designed to provide the
    user with information about who’s turn it is and if the game has been won or drawn. Our Tic-Tac-Toe View chooses to display that
    property via a Label control in the footer of the main window. Our Tic-Tac-Toe ViewModel also exposes commands for starting a
    new game and for when the user selects a square for their next move. Our Tic-Tac-Toe View chooses to have a menu item at the
    top of the main window that when chosen triggers the NewGame command of the ViewModel, whereas the Select square command
    is triggered when the user clicks one of the square user controls that is empty.
    The ViewModel also interacts with the Model, for example when the NewGame command is triggered it calls the GameStart function
    of the Model. Our model is implemented in a pure functional style, so it contains no mutable state. The ViewModel component
    however is stateful. It contains a private property called gameState that uses the Game type defined in the Tic-Tac-Toe Model
    component. When either the human or the computer makes a move, the ViewModel calls the ApplyMove function from the TicTac-Toe
    Model component to obtain a new Tic-Tac-Toe game object and overwrites the old value of the gameState property. The
    gameState property of the Tic-Tac-Toe ViewModel is mutable, while everything in the pure F# implementation of the Tic-Tac-Toe
    Model remains immutable.
    One of the nice things about having most of the presentation logic contained in the ViewModel and abstracted from the actual
    user interface is that we can easily perform automated unit tests and integration tests on the ViewModel as it does not involve a
    GUI. Our automated tests can directly trigger commands corresponding to abstract user actions and then observe how the state
    of the game and user interface changes by inspecting the properties that get directly bound to user interface elements. The
    TicTacToeViewModelTests Visual Studio project contains unit tests and integration tests designed to test the ViewModel.
    Multiple View Implementations
    The View is the only component of the application that depends on the technology used to create the user interface. In this app
    we choose to implement the View component using the Microsoft Windows Presentation Framework (WPF). The View needs to
    know about the ViewModel, but the ViewModel doesn’t need to know about the View. So, it is possible to have multiple
    alternative implementations of the View component. We could have implementations of the View using:
    WPF for use on Microsoft Windows Desktops,
    UWP for use on newer Microsoft platforms such as Windows 10, Xbox, Surface or Mobile devices,
    Xamarin for cross platform Android and IOS devices
    We could even create an implementation of the View that had a command line user interface rather than a graphical user
    interface.
    All of these different implementations of the View could reuse the exact same ViewModel and Model without needing to make
    any changes. There is nothing in the ViewModel or the Model that relates to WPF, UWP or Xamarin. In implementing the
    ViewModel and the View we have specifically targeted the new .NET Standard 2.0 (https://docs.microsoft.com/en…
    This open standard is supported by both Microsoft’s .NET Framework, but also by the open
    source .NET Core (https://en.wikipedia.org/wiki… which works across multiple platforms including Windows, IOS and
    Linux. Only the WPF View component is tied to the Microsoft Windows platform, but it could be easily replaced by a cross-platform
    alternative.
    View Binding
    The ViewModel doesn’t know about the View, but the View does need to know about the ViewModel. We generally try to connect
    the View to the ViewModel in a declarative manner. Firstly, the layout and components of the View’s user interface is specified in
    a declarative manner using a user interface mark-up language called XAML (pronounced Zamel)
    https://docs.microsoft.com/en…
    It is a tag based language (similar to HTML) that is used to specify which user interface elements are contained on the page and
    how they are laid out relative to one another.
    See for example TicTacToeMainWindow.xaml in the TicTacToeWPF Visual Studio project. We will see, for example, a Label named
    MessageLabel that is docked to the bottom of the main window. In the corresponding C# code behind file
    (TicTacToeMainWindow.cs) is the declarative code that binds this MessageLabel control of the View to the Message property of
    the ViewModel:
    this.Bind(this.ViewModel, vm => vm.Message, view => view.MessageLabel.Content);
    The Message property of the ViewModel is annotated with the Reactive attribute:
    [Reactive] public string Message {get; set;}
    Which means that whenever the set method of this property is called, it will automatically trigger a property changed event which
    will automatically notify all subscribed property change listeners (including the View), so the text displayed in the label control on
    the view will be automatically updated whenever the ViewModel changes the value of its Message property.
    Multiple Model Implementations
    Just like we could have multiple alternative implementations of the View (that all use the same ViewModel and View), similarly
    we could have multiple alternative implementations of the Tic-Tac-Toe Model (that all use the same ViewModel and Views). In
    our case we are actually going to create multiple alternative implementations of the Model for the purpose of comparing and
    contrasting different programming paradigms. We already have one pure F# implementation of the Model. You will also create a
    separate impure F# implementation of the Model (in the provided TicTacToeImpure.fs file) in which you will use mutable state
    to try to create a more efficient (faster) alternative implementation.
    The ApplyMove function of your pure F# implementation was of type: GameState->Move->GameState, however in your impure F#
    implementation you can make your GameState type mutable, i.e. when you apply a move, rather than returning a new GameState,
    the ApplyMove function changes the existing GameState. The impure ApplyMove function would be of type: GameState->Move-

    Unit (i.e. the function returns“void”rather than a new GameState. If that is the case, then you’ll probably also need to add an
    UndoMove function of type GameState->Move->Unit that undoes the state change (taking the square that was selected and
    changing it back to empty). Your impure F# implementation will therefore not be able to reuse the existing Minimax functions
    from the GameTheory library (since these are implicitly designed to work with immutable game state). So you will need to
    implement a new Minimax function (with alpha beta pruning). The implementation of this Minimax function can itself use mutable
    state (for example to progressively update the alpha and beta parameters) in order to create a more efficient implementation. It
    is not necessary, however, for this new Minimax function to be placed in a separate project, nor made generic to work for games
    other than Tic-Tac-Toe.
    You will also create a C# implementation of the Model (in the CSharpTicTacToeModels project) designed to showcase objectoriented
    design and implementation best practices.
    Since some of these model implementations are functional and others are object-oriented, in order for the ViewModel to make
    use of these different Models, we need to apply the Fa?ade design pattern (https://en.wikipedia.org/wiki… in order
    to provide a uniform interface. The TicTacToeInterfaces Visual Studio project defines such an interface. Each implementation
    of the Tic-Tac-Toe model will have its own data structures to represent: the current state of the Tic-Tac-Toe game (which might
    or might not be mutable), a Tic-Tac-Toe move and a Tic-Tac-Toe player. The Faade interface for the Tic-Tac-Toe Model is therefore
    a generic interface parameterized with the types used to represent the Tic-Tic-Toe Games, Moves and Players. Because the
    ViewModel also need to deal with these different Tic-Toe-Toe Games and Moves in a uniform manner, we also define an
    ITicTacToeGame and ITicTacToeMove interface that each of those types are required to implement (as appropriate).
    At the bottom of the TicTacToePure.fs file you will find implementations for these Facades. We actually want to expose two
    separate implementations, one that uses the basic Minimax algorithm and a second which uses the more efficient alpha beta
    pruning algorithm. These two implementations are the same except for that function, so we define an abstract base class called
    Model from which BasicMiniMax and AlphaBetaPruning are derived. Note, that these class definitions at the bottom of the file
    are provided only to provide a fa?ade to the ViewModel. In particular, we are not attempting to be object oriented in our
    implementation of the Pure F# Model – it consists purely of functions – not methods. Also, note how the Fa?ade classes don’t
    contain any real implementation code themselves. All the work is done in the F# functions defined above and the Fa?ade classes
    simply call those functions. The same should be true of the Fa?ade class in the impure F# implementation and in the C#
    implementation. In the case of the C# fa?ade class, it should simply call methods defined in the other domain classes – following
    principles of object-oriented design.
    The ViewModel class needs to hold a reference to one of these TicTacToeModel interfaces, however the interface is generic (with
    type parameters for the Game, Move and Player types). In order to avoid making the ViewModel a generic class, we instead split
    the ViewModel implementation into two parts. The fields and methods that need to deal with values of type TicTacToeGame,
    TicTacToeMove and TicTacToePlayer are moved into a separate ViewModel“child”class. The child class is generic, but the
    parent ViewModel class is not generic. In the constructor of the ViewModel class, an instance of this child class is created
    corresponding to each of the different Fa?ade classes providing alternative implementations of the model:
    // add pure F# model using basic MiniMax algorithm
    models.Add(new TicTacToeViewModelChild<FSharpPureTicTacToeModel.GameState,
    FSharpPureTicTacToeModel.Move,
    FSharpPureTicTacToeModel.Player>(this,
    new FSharpPureTicTacToeModel.BasicMiniMax()));
    // add pure F# model using MiniMax with alpha beta pruning
    models.Add(new TicTacToeViewModelChild<FSharpPureTicTacToeModel.GameState,
    FSharpPureTicTacToeModel.Move,
    FSharpPureTicTacToeModel.Player>(this,
    new FSharpPureTicTacToeModel.WithAlphaBetaPruning()));
    // add impure F# model using MiniMax with alpha beta pruning
    models.Add(new TicTacToeViewModelChild<FSharpImpureTicTacToeModel.GameState,
    FSharpImpureTicTacToeModel.Move,
    FSharpImpureTicTacToeModel.Player>(this,
    new FSharpImpureTicTacToeModel.WithAlphaBetaPruning()));
    // add impure C# model using MiniMax with alpha beta pruning
    models.Add(new TicTacToeViewModelChild<CSharpTicTacToe.Game,
    CSharpTicTacToe.Move,
    CSharpTicTacToe.Player>(this,
    new CSharpTicTacToe.WithAlphaBetaPruning()));
    This list of models contained in the ViewModel is bound to a Combo Box control in the view so that the user can dynamically select
    which implementation of the model they wish to make use. Whenever a new Model is chosen, a new game is automatically
    started, since the existing game state contained within the previous ViewModel child would not be compatible with the newly
    selected model. This method of abstracting what is provided by a particular component so that different implementations can be
    easily substituted is referred to as“dependency injection”(https://en.wikipedia.org/wiki…
    Node Counting
    In order to allow us to compare the performance statistics of these different model implementations we inject some diagnostic
    code into our model implementations. (Such diagnostic code would typical be commented out in the final“production”version of
    a system). The diagnostic code that we inject is designed to count how many search tree nodes we explore when performing the
    minimax algorithm. In particular, we want to be able to observe how many fewer nodes are explored if we enable the alpha beta
    pruning implementation. This diagnostic code is inherently stateful, so to avoid desecrating our pure F# implementation we wrap
    this code into a separate component contained in the NodeCounter Visual Studio project. Each of the model implementation
    projects will contain a reference to this project. All four implementations of the MiniMax function must make a single call to the
    Reset() method before performing the actual search and must call the Increment() method each time a new node of the search
    tree is explored. The ViewModel then uses the Count property of the NodeCounter to retrieve the total number of nodes visited
    after the call to the MiniMax function.
    The WPF view displays diagnostic information containing both the number of nodes explored and the time elapsed while
    searching. We expect the number of nodes explored to be the same regardless of whether we are using the F# pure version, the
    F# impure version or the C# version (assuming that in each case we are comparing the variant making use of alpha beta pruning),
    however the execution time for the C# implementation is likely to be faster and the F# impure version should be faster than the
    F# pure version.
    To run the final application, set TicTacToeWPF as the StartUp project and press Start.
    What to Submit

  4. A 1-2 page PDF report discussing your experience and comparing the three approaches (F# pure functional, F# impure
    functional and C# object-oriented imperative). Your comparison should include a discussion on the efficiency and
    effectiveness of the three approaches. You should discuss which was easier to program, which code is easier to read,
    understand and maintain, which is more concise and which produces more efficient code. Provide measures were
    applicable to support your claims.
  5. A zip file containing your entire Visual Studio Solution folder.
    You should work with the skeleton visual studio solution provided and make changes only to the following projects:
    GameTheory
    FSharpTicTacToeModels
    CSharpTicTacToeModels
    Note:
    All 41 occurrences of NotImplementedException should be replaced by an actual implementation.
    Extra helper functions and methods should be added as needed. Complex functions and methods should be
    broken down into simpler functions. Ensure you use meaningful names for all functions, methods, parameters
    and variables.
    Ideally, all 1959 tests should pass.
    To reduce file size when submitting you should remove the following:
    .vs folder
    packages folder
    bin folders
    obj folders
    Visual Studio solution files except for TicTacToe.sln
    Everything remaining should be added to a compressed zip file with a name of the form n1234567.zip
    Note: this must be a zip file, not a tar file, not a rar file, not an iso file, etc.
    When we mark your assignment we will:
  6. Unzip your zip file
  7. Double click on TicTacToe.sln to open your solution in Visual Studio 2017
  8. Perform a Rebuild Solution (this should cause any required packages to download as necessary).
  9. Run all of the tests via the Test Explorer Window
  10. Start your TicTacToeWPF application and test that it behaves as expected, selecting in turn each of the models
    from the drop down combo box, trying different game sizes and observing the performance diagnostics.
  11. We will then browse your source code and assess it against the assessment criteria.

    WX:codehelp

正文完
 0