(* Content-type: application/mathematica *) (*** Wolfram Notebook File ***) (* http://www.wolfram.com/nb *) (* CreatedBy='Mathematica 6.0' *) (*CacheID: 234*) (* Internal cache information: NotebookFileLineBreakTest NotebookFileLineBreakTest NotebookDataPosition[ 145, 7] NotebookDataLength[ 11719, 327] NotebookOptionsPosition[ 10959, 296] NotebookOutlinePosition[ 11321, 312] CellTagsIndexPosition[ 11278, 309] WindowFrame->Normal ContainsDynamic->False*) (* Beginning of Notebook Content *) Notebook[{ Cell[CellGroupData[{ Cell["Project - Game of Nim", "Title", CellChangeTimes->{{3.4185732253124523`*^9, 3.418573226971673*^9}, { 3.4185747845674963`*^9, 3.418574787299114*^9}, {3.449680473220893*^9, 3.449680478386063*^9}}], Cell["\<\ This project consists of playing the game of (normal play) Nim against the \ computer - you are to write the game. \ \>", "Text", CellChangeTimes->{{3.4185732474831343`*^9, 3.418573267866379*^9}, { 3.4187650127871*^9, 3.418765018163871*^9}}], Cell[CellGroupData[{ Cell["Game description", "Subsection", CellChangeTimes->{{3.418573271194646*^9, 3.418573285832707*^9}}], Cell[TextData[{ "A general game of Nim consists of ", StyleBox["k", FontSlant->"Italic"], " stacks, each of which has a set number of tokens. In each step, a player \ selects one heap, and then removes at least one token from that stack. The \ number of tokens taken can vary from 1 token to taking all tokens of that \ stack. The player to take the last token(s) wins (in normal play, which is \ the one you are to simulate. In the mis\[EGrave]re version, the player to \ take the last token loses).\n\nNim has been studied extensively, and a \ winning strategy for normal play Nim is known. To figure out which stack to \ choose and how many tokens to take, this is the procedure. Let ", Cell[BoxData[ FormBox[ SubscriptBox["h", "i"], TraditionalForm]]], " be the height of stack ", StyleBox["i", FontSlant->"Italic"], ".\n\n", StyleBox["Step 1: ", FontWeight->"Bold"], " Convert the heights of all the tokens into base 2.\n", StyleBox["Step 2: ", FontWeight->"Bold"], "Add the binary numbers without carry over (called digital sum). Let's call \ this value s. We denote this digital sum by s = ", Cell[BoxData[ FormBox[ SubscriptBox["h", "1"], TraditionalForm]]], " ", Cell[BoxData[ FormBox["\[CirclePlus]", TraditionalForm]]], " ", Cell[BoxData[ FormBox[ SubscriptBox["h", "2"], TraditionalForm]]], " ", Cell[BoxData[ FormBox["\[CirclePlus]", TraditionalForm]]], " ... ", Cell[BoxData[ FormBox["\[CirclePlus]", TraditionalForm]]], " ", Cell[BoxData[ FormBox[ SubscriptBox["h", "k"], TraditionalForm]]], ".\n\nIf this digital sum is 0, then the next player to play loses (if the \ game is played optimally). Thus, you need to make a move such that the \ digital sum ", StyleBox["after ", FontWeight->"Bold"], "your move is zero. This can be achieved by adding the non-zero value of the \ current digital sum s to a heap that has a 1 in the same column as the \ leftmost 1 of s. \n\nHere is an example:\n\ncurrent heaps: 12, 13, 7\n\n\t\t\t\ 12 = 1 1 0 ", Cell[BoxData[ FormBox[ SubscriptBox["0", "2"], TraditionalForm]]], "\n\t\t\t13 = 1 1 0 ", Cell[BoxData[ FormBox[ SubscriptBox["1", "2"], TraditionalForm]]], "\n\t\t\t 7 = 0 1 1 ", Cell[BoxData[ FormBox[ SubscriptBox["1", "2"], TraditionalForm]]], "\n s = ", Cell[BoxData[ FormBox[ SubscriptBox["h", "1"], TraditionalForm]]], " ", Cell[BoxData[ FormBox["\[CirclePlus]", TraditionalForm]]], " ", Cell[BoxData[ FormBox[ SubscriptBox["h", "2"], TraditionalForm]]], " ", Cell[BoxData[ FormBox["\[CirclePlus]", TraditionalForm]]], " ", Cell[BoxData[ FormBox[ SubscriptBox["h", "3"], TraditionalForm]]], " = ", StyleBox["0 1 1 ", FontWeight->"Bold"], Cell[BoxData[ FormBox[ SubscriptBox["0", "2"], TraditionalForm]], FontWeight->"Bold"], " (= ", StyleBox["6", FontWeight->"Bold"], " in decimal)" }], "Text", CellChangeTimes->{{3.418573288391788*^9, 3.4185733887080517`*^9}, { 3.4185734191025467`*^9, 3.4185734945410624`*^9}, {3.4185735256388283`*^9, 3.418573833679686*^9}, {3.4185738770843554`*^9, 3.418574116939498*^9}, { 3.41857418809172*^9, 3.418574198739757*^9}, {3.4185742869267807`*^9, 3.418574291806267*^9}, {3.418574342858556*^9, 3.41857435687638*^9}, { 3.418765024434869*^9, 3.418765105677547*^9}, {3.4203800301942873`*^9, 3.420380039054775*^9}, {3.420380116103635*^9, 3.420380220040154*^9}}], Cell[TextData[{ "Notice that the digital sum results in a 1 if there are an odd number of 1s \ in that column, and in 0 if there are an even number of 1s in that column.\n\n\ Back to the winning strategy. The leftmost 1 in s is in column 2 (if we label \ columns from left to right), and so we need to find one entry that has a 1 in \ that column too. In this case, we can pick any of the three heaps, i.e., \ there is a winning move from every heap. The player to move can reduce\n\n\ \[Star] the heap of 12 tokens to one of size ", Cell[BoxData[ FormBox["12", TraditionalForm]]], " ", Cell[BoxData[ FormBox["\[CirclePlus]", TraditionalForm]]], " ", Cell[BoxData[ FormBox["6", TraditionalForm]]], " = 10, or\n\[Star] the heap of 13 tokens to one of size ", Cell[BoxData[ FormBox["13", TraditionalForm]]], " ", Cell[BoxData[ FormBox["\[CirclePlus]", TraditionalForm]]], " ", Cell[BoxData[ FormBox["6", TraditionalForm]]], " = 11, or\n\[Star] the heap of 7 tokens to one of size ", Cell[BoxData[ FormBox["7", TraditionalForm]]], " ", Cell[BoxData[ FormBox["\[CirclePlus]", TraditionalForm]]], " ", Cell[BoxData[ FormBox["6", TraditionalForm]]], " = 1.\n\nHere is an example that illustates the above. If we choose the \ heap with 7 tokens, then we digitally add 7 and 6\n\n\t7 = 1 1 ", Cell[BoxData[ FormBox[ SubscriptBox["1", "2"], TraditionalForm]]], "\n\t6 = 1 1 ", Cell[BoxData[ FormBox[ SubscriptBox["0", "2"], TraditionalForm]]], "\n result = 0 0 ", Cell[BoxData[ FormBox[ SubscriptBox["1", "2"], TraditionalForm]]], " = 1 (in decimal)\n\nIn this case we reduce the stack of 7 tokens to one \ tokens, i.e., we take 6 tokens. \n\t\t\t" }], "Text", CellChangeTimes->{{3.4185741306405487`*^9, 3.418574507176518*^9}, { 3.420380278484343*^9, 3.420380463547258*^9}, {3.420380517469467*^9, 3.420380616501486*^9}}] }, Open ]], Cell[CellGroupData[{ Cell[TextData[StyleBox["Your Task", "Subsection"]], "Subsection", CellChangeTimes->{{3.418574568199366*^9, 3.418574594548842*^9}}], Cell[TextData[{ "Create a function that simulates a game between two players, where the \ first one (the human) plays randomly, i.e., randomly selects a stack, and \ then selects a random number of tokens from that stack. The second player \ (the computer) plays the optimal strategy. If the first player gets lucky \ and picks tokens in such a way that the digital sum becomes zero, then the \ computer also reverts to the random strategy. Visualize this game by an \ animation that shows a picture of the stacks at each step. For example, here \ would be an instance of a Nim game with heaps of sizes 3, 5 and 6. At the \ end of the game the function should pronounce which player won.\n\n\t\t\t\t", Cell[BoxData[ GraphicsBox[{DiskBox[{1, 1}, 0.45], DiskBox[{1, 2}, 0.45], DiskBox[{1, 3}, 0.45], DiskBox[{2, 1}, 0.45], DiskBox[{2, 2}, 0.45], DiskBox[{2, 3}, 0.45], DiskBox[{2, 4}, 0.45], DiskBox[{2, 5}, 0.45], DiskBox[{3, 1}, 0.45], DiskBox[{3, 2}, 0.45], DiskBox[{3, 3}, 0.45], DiskBox[{3, 4}, 0.45], DiskBox[{3, 5}, 0.45], DiskBox[{3, 6}, 0.45]}, ImageSize->{100.41940935283691`, Automatic}]], CellChangeTimes->{ 3.418575151156695*^9, {3.418575188534678*^9, 3.418575201849436*^9}, { 3.4185752546234417`*^9, 3.4185752687031183`*^9}}, TextAlignment->Center, ImageCache->GraphicsData["CompressedBitmap", "\<\ eJztmc1u00AQx9fY/aDloyBIhFBRFL6FOPACOUTQAgIOnHKNWqT2gEClT5D3 ypk3iJSnyCHXSItnvVOtlxJ745lskcZSa3v6y8xmP2bmr34enp98+z48Pz0a dg7Phj9PTo9+dQ5+nOWmNFFKHec/vzsqy591/uj8Otb5dXHbM7dULxYLPZ/P 4a4e1bTdLlzcMLdMTyYTPRqNdL/f1+12OzXRMng0JvhTjrQY6d1iQDt2rOPx WPd6PcPumN+peQc7EHeIue0i/LbFZ7OZHgwGBrxlcXgHOxA3ibnNIvyWxafT qe52uwbcszi8gx2IXWJuowi/6eCtVsuAdy0O74hfJ+ayIvyGM1k42nvOaHGy toi5tBzerpMB7ztrZa+LWaLirhXhM2enIt62uN2lzmTRcUk5vD0kJRxsvlsq zoZPLQ7JAvEHFgdbebIacAmYTFAvMuQh3yPYfI8rcwmYLosMWdD3CDbf48pc AqbLIkMO9j2Czfe4MpeAyY2MJNQiJB/aigA2vPLn/SXmBJ48l1DafJdgwyt/ 3l9iTuCJb5Txpjz+Not3tNafTiLn0chVJHINjdxBRO6fInePkXvnyMrhyikp AnUoclPkJmPCELkpclPkphK56XsUuSlys8E2E7lZeBS5ibjITZGbIjdFbsae JJGbIjdFbqr1NwoiN0VuKpGbbKMUuSlyU+Qm4iI3RW6K3PxP5OabsE+95v9u r3jW8CXPznzBc96e82SRZ86XI8yN6JY44z91VljR1TF0S1ydn1icrt1Aj3St E3qkawPRI11L+9iSdftztxHHz9aVC64uaBKXfhb4Vop+N9HteKajyZRImNIe U5JmKilMBZCpXDM1F2toiwIbtfJ/E6TLky6vcQKRLo+l5kmXp6TLky6v+dGU Lo+vpEiXp69+l/f13+CXVQbzKWx6PoYt0oewrfI+bMMehh0bxGse3gNnZmqk EMRrJrJ3Fq/OpEhWZ3EkqysIktXV662z35RbS92iidBfxdqtyrU81R9Y+Jet P4HVixK42oF7KXCnBp6DwFMWeIYDM0Rg/lkpxy3JmeXkqpI/xiWWeg==\ \>"]], "\n\nYour function should take as its argument the starting heaps, and \ should work with any number of stacks. Make sure that your function checks \ the arguments to be positive integers, and write a usage function and an \ error message for it. \n\n", StyleBox["Steps in developing your function:\n", FontWeight->"Bold"], "\n1) For a given set of stacks, create a display. \n2) Check out the \ functions ", StyleBox["IntegerDigits, FromDigits, ", FontWeight->"Bold"], " and ", StyleBox["Mod", FontWeight->"Bold"], " for writing a function that adds values digitally.\n3)", StyleBox[" ", FontWeight->"Bold"], "The functions ", StyleBox["Select", FontWeight->"Bold"], " and ", StyleBox["Position", FontWeight->"Bold"], " are useful for determining which stack to use for the optimal move.\n4) \ You can use the function ", StyleBox["Input", FontWeight->"Bold"], " to ask for the user input. \n5) Your function should have a loop inside of \ it to test whether all stacks are empty to determine whether the game is \ over. You also need to keep track of who is playing in order to determine who \ has won.\n" }], "Text", CellChangeTimes->{{3.418574607717126*^9, 3.418574800170788*^9}, { 3.418575298547083*^9, 3.418575354366137*^9}, {3.41876519895905*^9, 3.418765283530867*^9}, {3.418765411272079*^9, 3.41876551369636*^9}, 3.420380634731216*^9, {3.420380808484088*^9, 3.420380860454913*^9}, { 3.420380921801916*^9, 3.4203810490601397`*^9}, {3.4203811320962887`*^9, 3.42038121093858*^9}}] }, Open ]], Cell[CellGroupData[{ Cell["References", "Subsection", CellChangeTimes->{{3.4187655259023952`*^9, 3.4187655298621407`*^9}}], Cell["http : // en.wikipedia.org/wiki/Nim", "Text"], Cell["", "Text", CellChangeTimes->{{3.420380791983981*^9, 3.420380803019215*^9}}] }, Open ]] }, Open ]] }, WindowSize->{640, 706}, WindowMargins->{{12, Automatic}, {Automatic, 24}}, ShowSelection->True, FrontEndVersion->"6.0 for Mac OS X PowerPC (32-bit) (April 20, 2007)", StyleDefinitions->"Default.nb" ] (* End of Notebook Content *) (* Internal cache information *) (*CellTagsOutline CellTagsIndex->{} *) (*CellTagsIndex CellTagsIndex->{} *) (*NotebookFileOutline Notebook[{ Cell[CellGroupData[{ Cell[590, 23, 206, 3, 76, "Title"], Cell[799, 28, 254, 5, 41, "Text"], Cell[CellGroupData[{ Cell[1078, 37, 104, 1, 34, "Subsection"], Cell[1185, 40, 3418, 102, 373, "Text"], Cell[4606, 144, 1887, 52, 296, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[6530, 201, 131, 1, 34, "Subsection"], Cell[6664, 204, 3989, 77, 558, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[10690, 286, 102, 1, 34, "Subsection"], Cell[10795, 289, 51, 0, 26, "Text"], Cell[10849, 291, 82, 1, 26, "Text"] }, Open ]] }, Open ]] } ] *) (* End of internal cache information *)