nim game

Write a program that will generate a tree of all of the legal moves for a *nim* game that begins from the position 123. After generating the tree, you are to use the rules given below to allow your program to analyze the tree and compute the *perfect game* moves. And finally, you are to arrange for your program to play 5 games against a human (stdin) player. That is, you have *three* things to do: generate the tree of moves, mark the paths that win for the computer, and play 5 games. **PLEASE CHECK ON ATTACHED ZIP FILE FOR COMPLETE DESCRIPTION OF PROGRAM.** **We are constrained to use a *tree*. It is not a binary tree. USE STANDARD INPUT ONLY. USE JAVA CODING ONLY **Each node in the tree can have up to six (6) children, although most will have only one or two. The tree is easiest if you start at the top, **but build it from the bottom up, recursively.** The game of ***nim*** is one of several games (tic-tac-toe, hexapawn, etc.) that are used to introduce game-theory, machine learning, and artificial intelligence concepts. It is a *zero-sum* game. This is just a fancy mathematical way of saying that the games cannot result in a tie; which makes it much easier to write programs to analyze, play, and evaluate the game. ## Deliverables *Nim* is played by placing three rows of some number of like objects, one above the other. | | | | | | For practical reasons, when used for purposes of computing exposition, the number of elements in any single row is restricted to 0 thru 9 (1 thru 9 to begin the game). Among other things, this allows us to describe a *nim* game state with a three digit number (e.g. 345) in which each digit specifies the current number of items in the lines from the top to bottom. The game progresses with first one player and then the other removing some number of items from any single row. That is, if there are 3 items in a particular row, then a player is allowed to remove 1, 2, or 3 (all) of those items. The game is over when there are no more items to remove, and the player that removed the final item(s) is the winner. For the purposes of computer exposition, we usually let a human player compete against a computer program, and we always let the human player go first. A typical game, with an initial board of 123, might proceed in the following way: board is (123) initial board board is (23) player removes entire top row (1 item) board is (22) computer removes one (1) item from row board is (20) player removes entire bottom row (2) computer wins computer removes entire middle row (2 items) In addition to being a *zero-sum* game, when *nim* is played within the sizes we have specified, it is a completely computable game. That is, if the starting position is known, a programmer can analyze that position and write a program that will play *perfectly* (i.e. win every game, no matter what the human player does). Furthermore, the solution set for such games is small enough that the analysis phase can be written into the program so it can analyze any legal starting position and generate the data structures necessary to play perfectly. The game is also amenable to *learning* strategies. So that if enough games are played from a single starting position, a computer program can modify its data structures in such a way that it plays progressively better and better. This figure presents a very small part of the eventual game tree for the *nim* game, the one beginning with 123. Notice that nodes have a variable number of children (from 0 to 6). Notice too that all leaf nodes have the value 0 and every node with a value of 0 is a leaf node. Each node in the tree will have to be a *class*, as with all Java linked structures. At a minimum it will have to contain the relevant board position, room for up to six child pointers, and an integer to hold our winning game analysis results. Looking at the tree diagram shown above, we will say that the root of the tree is *level 0*. The next lower level (the one with nodes 23, 103, 113, 120, 121, and 122 on it) is *level 1*, and so on down the tree. That makes the level with the two 0 nodes on it *level 4*. With that in mind, we can analyze the tree and mark the nodes in the following way: - a 0 node on an *even* level is marked as +1. - a 0 node on an *odd* level is marked as -1. - for an interior node on an *even* level, if *any* node in the subtree below it is marked -1, then this node is marked -1, otherwise it is marked +1. - for an interior node on an *odd* level, if *any* node in the subtree below it is marked +1, then this node is marked +1, otherwise it is marked [login to view URL] this process proceeding upward from every leaf to the root. A partial result is reflected in the updated figure below. ## Platform The computer's strategy will be to always move from its present position to a node on the next lower level that is marked with a +1. If, for example, the player moves from 123 to 121 (see the tree diagram), then the computer will choose to move to 101, which is the only +1 move available to it at that point. The player is then forced to move to either 1 or 100, and the computer wins on the next move. 1) complete source code of all work done. 2) in ready-to-run condition on the platform specified in this bid request. 3) Exclusive and complete copyrights to all work purchased. (No GPL, 3rd party components, etc. unless all copyright ramifications are explained AND AGREED TO by the buyer on the site). 4) code should be authentic and made exclusively only for me. 5) use only JAVA. 6) **USE STANDARD INPUT ONLY.** JAVA ONLY