; ----------------------------------------------------
; This is a program to play the graph game of Sim
; which was invented (or reinvented) by
; Gustavus J. Simmons and described in his 1969
; paper in the JOURNAL OF RECREATIONAL MATHEMATICS.
; In the graph game of Sim, two players alternate
; drawing lines of their own color in a graph
; initially consisting of six points -- no three of
; which are colinear. The first player to make a
; triangle of their color loses.
; The 6_choose_2 = 15 possible moves are denoted by
; 12, 13, 14, 15, 16,
; 23, 24, 25, 26,
; 34, 35, 36,
; 45, 46,
; and 56
; where the move xy means joining the graph nodes
; x and y.
; Various heuristic approaches (or rules of thumb)
; to playing Sim have been used. Two are used in the
; two levels of play that this program offers.
;
; The beginner-mode uses random moves except that
; it will not make a triangle. This approach is
; similar to that used by Moore in his 1987 paper
; in the JOURNAL OF RECREATION MATHEMATICS.
;
; The experienced-mode uses (essentially) the
; approach taken by Rounds and Yau in their 1974
; paper in the JOURNAL OF RECREATIONAL MATHEMATICS.
; More information on Sim may be found in
; Martin Gardner's columns in the Jan-1973 and
; May-1973 issues of SCIENTIFIC AMERICAN or his
; KNOTTED DOUGHNUTS AND OTHER
; MATHEMATICAL ENTERTAINMENTS.
;
; More detailed information can be found in
; MATHEMATICAL SOLITAIRES AND GAMES,
; edited by Benjamin L. Schwartz and some
; other references mentioned at
; http://sciences.aum.edu/mh/faculty/furman/sim.html
; -- a site maintained by this programmer
; who teaches mathematical subjects
; at Auburn University at Montgomery.
; This program is in the MicroWorlds 2 version of
; the computer language Logo.
; The URL above also has a link to the MicroWorlds
; program. When MicroWorlds starts, it looks for a
; procedure named "startup" and obeys it first;
; if you want to read the program, start with startup.
; Note that the proceedures are listed in alphabetical
; order.
; This program is in the public domain. If you use
; substantial portions of it, it would be polite to
; give proper credit; refering to the URL above is
; one way to give sufficient credit.
;
; Happy programming -- in whatever language.
; ======================================================
; ----------------------------------------------------
to clear_the_canvas
ifelse :board = "Sim
[clean]
[ dolist
[j :initial_possible_moves]
[talkto word "t :j
st
setc "white
fill]
]
talkto "left_side_box
cleartext
talkto "right_side_box
right_side_box, cleartext
carefully [remove "Again_button] []
carefully [remove "Quit_button] []
end
; ----------------------------------------------------
to console
talkto "right_side_box
cleartext
insert [It takes practice to beat me.]
invite_another_game
end
; ----------------------------------------------------
to continue_play
get_move_from_user
if not legal_move?
[list_legal_moves
continue_play]
update_board
if game_over?
[console
stopall]
update_lists
respond
update_board
if game_over?
[praise
stopall]
update_lists
continue_play
end
; ----------------------------------------------------
to game_over?
ifelse :current_player = "user
[output
not member? :move :feasible_moves_for_user]
[output
not member? :move :feasible_moves_for_program]
end
; ----------------------------------------------------
to get_move_from_user
make "current_player "user
make "input_for_move "
prompt_for_user's_move
wait_until_move_specified
make "move :input_for_move
if ( ( first :move ) = ( last :move ) )
[talkto "left_side_box
cleartext
insert [Please click two turtles.]
get_move_from_user ]
if ( ( first :move ) > ( last :move ) )
[make "move word last :move first :move]
talkto "left_side_box
cleartext
talkto "right_side_box
cleartext
end
; ----------------------------------------------------
to initialize_lists
; A move is considered feasible here if it does not
; immediately result in a triangle.
make "initial_possible_moves
[ 12 13 14 15 16
23 24 25 26 34
35 36 45 46 56]
make
"feasible_moves_for_user
:initial_possible_moves
make
"feasible_moves_for_program
:initial_possible_moves
repeat 6
[make "feasible_moves_for_program
sorta_shuffled
:feasible_moves_for_program]
make "chosen_by_user []
make "chosen_by_program []
make "text_gap word char 32 char 32
end
; ----------------------------------------------------
to introduce_game
ifelse :board = "Tri_Not
[getpage "Intro_Tri_Not]
[getpage "page1]
stopall
; This is the end of one sequence of proceedures.
; What comes next depends on which of the buttons
; on page1 the user clicks on. For example, clicking
; on the upper left button initiates the single instruction
; to execute the procedure "You_first._Be_easy.".
end
; ----------------------------------------------------
to invite_another_game
newbutton "Again_button [ -200 -125]
[Play_again.]
newbutton "Quit_button [ 100 -125]
[Quit.]
recycle
stopall; <-- What's next depends on which button clicked.
end
; ----------------------------------------------------
to legal_move?
output member? :move :feasible_moves_for_user
end
; ----------------------------------------------------
to let_the_game_begin
initialize_lists
getpage word :board "_board
clear_the_canvas
if :current_player = "program
[make "move pick :feasible_moves_for_program
update_board
update_lists]
continue_play
end
; ----------------------------------------------------
to list_legal_moves
ifelse (count :feasible_moves_for_user) > 0
[talkto "right_side_box
cleartext
insert sentence
[That is not a good move. Better moves include: ]
:feasible_moves_for_user
insert ".
]
[talkto "left_side_box
cleartext
insert [You have lost.]
console
stopall
]
end
; ----------------------------------------------------
to makes_triangle? :a_move :list_of_moves_of_this_color
; From the value of :move, get the names of the
; points associated with that move;
; a move of xy is the line joining points x and y.
make "x first :a_move
make "y butfirst :a_move
; If the move xy makes a triangle, there is a point
; z such that there is a line joining x and z and
; also a line joining y and z. Consider all
; possible z's : z = 1, 2, ..., 6.
dolist
[ z [ 1 2 3 4 5 6 ] ]
[
;Put lines into cannonical terminology; ;that is,
;we have a line 35 but no line is called ;53.
ifelse :x < :z [make "line_1 word :x :z]
[make "line_1 word :z :x]
ifelse :y < :z [make "line_2 word :y :z]
[make "line_2 word :z :y]
;See if move xy will join two lines of the
;color being considered.
if and
member? :line_1 :list_of_moves_of_this_color
member? :line_2 :list_of_moves_of_this_color
[output "true]
]
output "false
end
; ----------------------------------------------------
to Play_again.
introduce_game
end
; ----------------------------------------------------
to praise
talkto "left_side_box
cleartext
insert [You won. You WON! YOU WON! Good job.]
invite_another_game
end
; ----------------------------------------------------
to prompt_for_user's_move
talkto "left_side_box
cleartext
insert [Your turn.]
insert :text_gap
ifelse :board = "Sim
[insert [ Click on two blobs to draw your red line.]]
[insert [ Click on one blob to color it red.] ]
insert :text_gap
insert [ You do NOT want to make a red triangle.]
end
; ----------------------------------------------------
to Quit.
clear_the_canvas
announce [I've enjoyed it. Goodbye.]
recycle
stopall
end
; ----------------------------------------------------
to respond
talkto "left_side_box
cleartext
insert [My turn. I am thinking where to draw my blue.]
make "current_player "program
ifelse :level_of_play = "easy
[respond_easy]
[respond_hard]
talkto "left_side_box
cleartext
end
; ----------------------------------------------------
to respond_easy
if (count :feasible_moves_for_program) = 0
[praise]
make "move first :feasible_moves_for_program
if makes_triangle? :move :chosen_by_program
[make "feasible_moves_for_program
butfirst :feasible_moves_for_program
respond_easy]
end
; ----------------------------------------------------
to respond_hard
make "best_value -100 ; Anything is better than that.
if (count :feasible_moves_for_program) = 0
[praise]
ifelse
(count :feasible_moves_for_program)
<
(count :feasible_moves_for_user)
[make "benefit_of_taking_an_option_from_user .5]
[make "benefit_of_taking_an_option_from_user 1.5]
dolist
[ j :feasible_moves_for_program ]
[ make
"how_many_feasible_moves_we_would_have
count updated_feasible "program :j
ifelse member? :j :feasible_moves_for_user
[ make
"estimated_goodness
:how_many_feasible_moves_we_would_have +
:benefit_of_taking_an_option_from_user ]
[ make
"estimated_goodness
:how_many_feasible_moves_we_would_have ]
if :estimated_goodness > :best_value
[ make "best_value :estimated_goodness
make "best_move :j ]
]
make "move :best_move
end
; ----------------------------------------------------
to sorta_shuffled :list
; This proceedure is called sorta_shuffled since
; it does not result in a perfectly shuffled list.
ifelse empty? :list
[output []]
[ifelse (random 2) = 0
[output
sentence first :list sorta_shuffled butfirst :list]
[output
sentence last :list sorta_shuffled butlast :list]
]
end
; ----------------------------------------------------
to startup ;-------- *** --- This is done first.
; presentationmode
make "board "Sim
introduce_game
end
; ----------------------------------------------------
to Tell_me_about_Sim_again.
make "board "Sim
getpage "page1
stopall
end
; ----------------------------------------------------
to Tell_me_about_Tri_Not.
make "board "Tri_Not
getpage "Intro_Tri_Not
stopall
end
; ----------------------------------------------------
to update_board
run word "update_board_for_ :board
end
; ----------------------------------------------------
to update_board_for_Sim
make "start_turtle word "t first :move
make "end_turtle word "t last :move
talkto :start_turtle
make "start_pos pos
talkto :end_turtle
make "end_pos pos
talkto "t0
pu
setpos :start_pos
pd
towards :end_turtle
ifelse :current_player = "user
[ setc "red ]
[ setc "blue ]
glide
item
( 3 - abs ( 3 - ( last :move - first :move ) ) )
[ 105 182 210 ]
5
pu
end
; ----------------------------------------------------
to update_board_for_Tri_Not
talkto word "t :move
ht
ifelse :current_player = "user
[setc "red ]
[setc "blue ]
fill
end
; ----------------------------------------------------
to update_lists
; Add the move that the current_player just made to the list
; of moves made by the current_player. For example, if the user
; has just chosen 12,
; then we add 12 to the list "chosen_by_user.
make
(word "chosen_by_ :current_player)
sentence
:move
thing (word "chosen_by_ :current_player)
; Whatever move was made is no longer an option for
; the either player.
make "feasible_moves_for_user
yanked_from_list :move :feasible_moves_for_user
make "feasible_moves_for_program
yanked_from_list :move :feasible_moves_for_program
; There might be moves that were feasible for the
; current_player before the player's move but are no
; longer feasible. For example, suppose the user
; took line 12 as the first move. At that point, the
; line 23 certainly is a feasible move. If the user's
; second move is 13, however, the line 23 ceases
; to be feasible.
make
word "feasible_moves_for_ :current_player
updated_feasible :current_player :move
end
; ----------------------------------------------------
to updated_feasible :a_player :a_move
; This next command is sometimes a duplication of effort
; but I can live with it and I don't see how to live without
; it without complicating the code more than it is worth.
make
"hypothetical_feasible
yanked_from_list
:a_move
thing word "feasible_moves_for_ :a_player
make
"hypothetical_chosen
sentence
:a_move
thing word "chosen_by_ :a_player
; The logic behind the following is documented in the
; procedure update_lists .
dolist
[j :hypothetical_feasible]
[if makes_triangle?
:j
:hypothetical_chosen
[make "hypothetical_feasible
yanked_from_list
:j
:hypothetical_feasible]
]
output :hypothetical_feasible
end
; ----------------------------------------------------
to wait_until_move_specified ;-----------------------
;
; A less robust version of this program would not have
; the variable "input_for_move but would use "move
; instead. The disadvantage of this reasonable approach
; is that a hostile user could click on, say, four turtles
; which would change the meaning of "move in the
; midst of calculations.
recycle
if ((count :input_for_move) = 2) [stop]
wait_until_move_specified
end
; ----------------------------------------------------
to yanked_from_list :item :list
; The item might be in the list zero, one, or more
; times. All occurences are removed.
ifelse :list = []
[ output [] ]
[ ifelse (first :list) = :item
[ output
yanked_from_list :item butfirst :list ]
[ output
sentence
first :list
yanked_from_list :item butfirst :list ]
]
end
; ----------------------------------------------------
to You_1st._Be_easy.
make "current_player "program
make "level_of_play "easy
let_the_game_begin
end
; ----------------------------------------------------
to You_1st._Play_hard.
make "current_player "program
make "level_of_play "hard
let_the_game_begin
end
; ----------------------------------------------------
to You_2nd._Be_easy.
make "current_player "user
make "level_of_play "easy
let_the_game_begin
end
; ----------------------------------------------------
to You_2nd._Play_hard.
make "current_player "user
make "level_of_play "hard
let_the_game_begin
end
; --------- end of procedures for sim program ---
; Sat, 28-Mar-1998, version of sim.mw2