home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / historic / v941.tgz / icon.v941src.tar / icon.v941src / ipl / progs / nim.icn < prev    next >
Text File  |  2000-07-29  |  9KB  |  320 lines
  1. ############################################################################
  2. #
  3. #    File:     nim.icn
  4. #
  5. #    Subject:  Program to play the game of nim
  6. #
  7. #    Author:   Jerry Nowlin
  8. #
  9. #    Date:     June 14, 1994
  10. #
  11. ############################################################################
  12. #
  13. #   This file is in the public domain.
  14. #
  15. ############################################################################
  16. #
  17. # The game of nim focuses on a pile of 15 sticks.  Each player can
  18. # select 1, 2, or 3 sticks from the sticks remaining in the pile when
  19. # it's their turn.  The player to pick up the last stick(s) wins.  The
  20. # loser of the previous game always gets to go first.
  21. #
  22. # There are two versions of nim in here.  The first (default) version
  23. # uses an algorithm to make its moves.  It will never lose if it gets
  24. # the first turn.  The second version tries to learn from each game.
  25. # You'll have to play a few games before it will get very smart but
  26. # after a while it will also never lose if it gets the first turn.  This
  27. # is assuming of course that you know how to play.  Since the learning
  28. # version learns from the person it plays against, if you're lousy the
  29. # game will be too.
  30. #
  31. # To invoke the learning version just pass any argument to the program.
  32. # If you want to see how the program learns, you can use the string
  33. # "show" as the argument and the program's current game memory will be
  34. # displayed after each game.  If you invoke the game with the string save
  35. # as an argument a file called ".nimdump" will be created in the current
  36. # directory with a dump of the program's game memory when you quit and
  37. # the next time the game is played in learn mode it will initialize its
  38. # game memory from the dump.  You can invoke this program with more than
  39. # one argument so show and save can be used at the same time.
  40. #
  41. ############################################################################
  42. #
  43. #  Links:  random
  44. #
  45. ############################################################################
  46.  
  47. link random
  48.  
  49. global    STICKS,    # the number of stick left
  50.     MINE,    # my trys for a given game
  51.     THEIRS,    # their trys for a given game
  52.     TRIED    # the combined tried table (game memory)
  53.  
  54. procedure main(args)
  55.  
  56.     local    resp,    # player response
  57.         turn,    # who's turn
  58.         fp,    # file pointer
  59.         stick,    # sticks index
  60.         take,    # take index
  61.         seed,    # random number seed
  62.         show    # show the game memory flag
  63.  
  64.         randomize()
  65.  
  66.     # check if we should show the thought process of a learning game
  67.     if !args == "show" then show := "yes"
  68.  
  69.     # define game memory
  70.     TRIED := table()
  71.  
  72.     # if this is a learning game and there's a memory dump read it
  73.     if *args > 0 & fp := open(".nimdump","r") then {
  74.         every stick := 1 to 15 do {
  75.             TRIED[stick] := list(3)
  76.             every take := 1 to 3 do
  77.                 TRIED[stick][take] := (read(fp) | "?")
  78.         }
  79.         close(fp)
  80.     }
  81.  
  82.     # otherwise initialize game memory to unknowns
  83.     else every stick := 1 to 15 do TRIED[stick] := [ "?", "?", "?" ]
  84.  
  85.     # start with their turn
  86.     turn := "theirs"
  87.  
  88.     # print the initial message
  89.     write("\nThis is the game of nim.  You must pick up 1, 2 or 3")
  90.     write("sticks from the pile when it's your turn.  The player")
  91.     write("that picks up the last stick(s) wins.  Good luck.")
  92.  
  93.     # loop
  94.     repeat {
  95.  
  96.         # initialize the per game variables
  97.         STICKS := 15
  98.         THEIRS := table()
  99.         MINE := table()
  100.  
  101.         # display the initial stick pile
  102.         dispile()
  103.  
  104.         # loop while there are sticks left
  105.         while STICKS > 0 do
  106.  
  107.             # take turns
  108.             if turn == "theirs" then
  109.                 turn := theirturn(args)
  110.             else    turn := myturn(args)
  111.  
  112.         # the player who took the last stick(s) wins
  113.         if turn == "theirs" then
  114.             write("\nI won!")
  115.         else    write("\nYou won!")
  116.  
  117.         # if this is a thinking game learn from it
  118.         if *args > 0 then learn(turn,show)
  119.  
  120.         # see if they want to play again
  121.         writes("\nDo you want to play again? ")
  122.         if not any('yY',read()) then quit(args,"\nGoodbye.\n")
  123.     }
  124. end
  125.  
  126. procedure theirturn(args)
  127.  
  128.     local    pick    # the players pick
  129.  
  130.     # find out how many sticks they want
  131.     writes("How many sticks do you want? ")
  132.     pick := read()
  133.  
  134.     # check their response to see if they want to quit
  135.     if any('qQ',pick) then quit(args,"\nYou gave up!\n")
  136.  
  137.     # check to see if their pick is valid
  138.     if not numeric(pick) | pick < 1 | pick > (3 | STICKS) then
  139.         write("\007Invalid Response\007\n") & return "theirs"
  140.  
  141.     # save their pick if this is a thinking game
  142.     if *args > 0 then THEIRS[STICKS] := pick
  143.  
  144.     # take away the sticks
  145.     STICKS -:= pick
  146.  
  147.     # if there are any sticks left display them
  148.     if STICKS > 0 then dispile()
  149.  
  150.     # make it my turn
  151.     return "mine"
  152. end
  153.  
  154. procedure myturn(args)
  155.  
  156.     local    pick    # my pick
  157.  
  158.     # let them know I'm about to pick
  159.     writes("I'll take ")
  160.  
  161.     # make my choice depending on whether or not this is a thinking game
  162.     if *args > 0 then {
  163.  
  164.         # think about it
  165.         pick := thinkpick(STICKS)
  166.  
  167.         # if I can't make up my mind randomly pick one choice
  168.         if type(pick) == "list" then pick := ?pick
  169.  
  170.         MINE[STICKS] := pick
  171.  
  172.     } else    pick := algorpick(STICKS)
  173.  
  174.     # tell them what I decided
  175.     write((1 < pick) || " sticks." | "1 stick.")
  176.  
  177.     # take away the sticks
  178.     STICKS -:= pick
  179.  
  180.     # if there are any sticks left display them
  181.     if STICKS > 0 then dispile()
  182.  
  183.     # make it their turn
  184.     return "theirs"
  185. end
  186.  
  187. procedure dispile()
  188.     write()
  189.     every 1 to STICKS do writes("/ ")
  190.     write("\n")
  191. end
  192.  
  193. # Use an algorithmic method to choose the number of sticks I want.  The
  194. # decision is made by taking the number of sticks that will leave an even
  195. # multiple of 4 in the pile (0 is an even multiple of 4) if possible and if
  196. # not then randomly choose 1, 2 or 3 sticks.
  197.  
  198. procedure algorpick(sticks)
  199.     return (0 ~= (sticks % 4)) | ?3
  200. end
  201.  
  202. # Use a learning method to choose the number of sticks I want.  The
  203. # decision is made by looking at the choices that have been made for this
  204. # number of sticks in the past and the results of the game where it was
  205. # made.  If there is no pick that resulted in a win make a random pick
  206. # from all the unknown picks.  If there are no unknown picks just randomly
  207. # choose 1, 2 or 3 sticks and hope THEY screw up.
  208.  
  209. procedure thinkpick(sticks,recurse)
  210.  
  211.     local    picks,    # unknown picks
  212.         take,    # take index
  213.         check,    # check list
  214.         pick    # my pick
  215.  
  216.     # initialize a list of unknown picks
  217.     picks := []
  218.  
  219.     # check every possible pick
  220.     every take := 1 to 3 do {
  221.  
  222.         # if this pick won take it
  223.         if TRIED[sticks][take] == "won" then return take
  224.  
  225.         # if this pick is unknown save it
  226.         if TRIED[sticks][take] == "?" then put(picks,take)
  227.     }
  228.  
  229.     # if there are no unknown picks and no winning picks anything goes
  230.     if *picks = 0 then picks := [1,2,3]
  231.  
  232.     # be smarter and check to see if there is a clear win for THEM
  233.     # after any of the picks left
  234.     if /recurse then {
  235.         check := []
  236.         every pick := !picks do
  237.             if type(thinkpick(0 < (sticks - pick),1)) == "list" then
  238.                 put(check,pick)
  239.         if *check = 0 then
  240.             picks := [1,2,3]
  241.         else    picks := check
  242.     }
  243.  
  244.     return picks
  245. end
  246.  
  247. # Save the results of each pick in this game in the programs game memory and
  248. # if the command line argument was "show" display the updated game memory.
  249.  
  250. procedure learn(turn,show)
  251.  
  252.     local    them,    # their outcome flag
  253.         me,    # my outcome flag
  254.         stick,    # sticks index
  255.         take    # taken index
  256.  
  257.     # decide on the outcome
  258.     if turn == "theirs" then
  259.         them := "lost" & me := "won"
  260.     else    them := "won" & me := "lost"
  261.  
  262.     # check for all the picks made for this game and save the results
  263.     # in the game memory
  264.     every stick := 1 to 15 do {
  265.         if \MINE[stick] then
  266.             TRIED[stick][MINE[stick]] :=
  267.                 comp(TRIED[stick][MINE[stick]],me)
  268.         if \THEIRS[stick] then
  269.             TRIED[stick][THEIRS[stick]] :=
  270.                 comp(TRIED[stick][THEIRS[stick]],them)
  271.     }
  272.  
  273.     # if the show flag is set print the program's game memory
  274.     if \show then {
  275.         writes("\n               picks\n          ")
  276.         every writes(center(1 to 3,5))
  277.         write("\n         ----------------")
  278.         every stick := 15 to 1 by -1 do {
  279.             if stick = 8 then
  280.                 writes("sticks ",right(stick,2),"|")
  281.             else    writes("       ",right(stick,2),"|")
  282.             every take := 1 to 3 do
  283.                 writes(center(TRIED[stick][take],5))
  284.             write()
  285.         }
  286.     }
  287.  
  288.     return
  289. end
  290.  
  291. # Compare this game's result with what the program remembers.  If the results
  292. # were the same fine.  If the old result was unknown save the new result.  If
  293. # the old result is different from the new result the game can't know for
  294. # sure anymore so go back to unknown.
  295.  
  296. procedure comp(old,new)
  297.  
  298.     return (old == new) | (old == "?" & new) | "?"
  299.  
  300. end
  301.  
  302. procedure quit(args,msg)
  303.  
  304.     local    fp,    # file pointer
  305.         stick,    # sticks index
  306.         take    # take index
  307.  
  308.     write(msg)
  309.  
  310.     if !args == "save" then
  311.         if fp := open(".nimdump","w") then {
  312.             every stick := 1 to 15 do
  313.                 every take := 1 to 3 do
  314.                     write(fp,TRIED[stick][take])
  315.             close(fp)
  316.         }
  317.  
  318.     exit()
  319. end
  320.