Morpion solitaire/Unicon: Difference between revisions
m
Fixed syntax highlighting.
m (→Game Logging: fix hdr) |
m (Fixed syntax highlighting.) |
||
| (22 intermediate revisions by one other user not shown) | |||
Line 1:
This example goes beyond the task goal of playing a random game of Morpion solitaire. The code is divided into two sections (a) to support the basic task and (b) extensions. The program was designed as a first cut/test bed more for understanding and exploring the problem space rather than for high efficiency. The program is structured to allow its behaviour to be configured (see options and M_ vars). Some of the features and extensions include:
* Playing single games or running multigame simulations to find and capture the best games
* Producing re-loadable game records and the ability to replay a saved game from a given position forward
Line 7:
* Plugable modules for functions including applying player strategy, position evaluation (fitness/heuristics)to facilitate quick experimentation, changing game read/write functions, etc., etc.
Using random play in many summary runs, the highest (5T) score achieved was 92. While it was fairly easy to push random games into the low 80's running simulations of as little as a few hundred games, going beyond the highest score without adding some smarts will require some very long runs and is unlikely to result in any significant progress. Observing multigame runs show that play advances fairly quickly before
The ability to replay recorded games provides a way to study the behaviour of the problem. Selecting successful random games, truncating them and running multigame simulations using a successful base shows that the seeds of success are sown early. It was possible to better the results of good random game scores (mid 80s) pushing the new scores up into the mid 90s. Unfortunately this technique when applied to Chris Rosin's 177 move record game did not produce any new records :(. Surprisingly however, it was possible to produce games in the high 160's! using random play with a truncated (approx 60%) version of this game.
Line 23:
For more see: Morpion -h|-help
==
The code need to solve the task requirements is found in this section. Just delete the $define below. The basic code will play a single random game, show an ASCII art grid, and produce a log in Pentasol compatible notation. On any given run your most likely to see a game with scores in the 20's or 60's.
===Main and Core Game Play Procedures===
<syntaxhighlight lang="unicon">link printf,strings,options
$define MORPVER "1.
$define EXTENDED 1 # delete line for basic
procedure main(A)
$ifdef EXTENDED
MorpionConf(A) # conf extended version
if \M_ReplayFile then ReplayMorpion()
else if \M_Limit === 1 then ShowGame(SingleMorpion())
else MultiMorphion(\M_Limit)
$else
printf("--- Morpion Solitaire 5 (v%s) (single random game)---\n\n",MORPVER)
M_Strategy := RandomPlayer
M_Mvalid := ValidMove5T # can be changed to 5D
M_WriteGame := WriteMoveLogPS
M_Output := &output
ShowGame(SingleMorpion())
$endif
end
$define XEMPTY "."
$define XINIT "*"
$define XUSED "+"
$define DHOR "-"
$define DVER "|"
$define DRD "\\"
$define DLD "/"
$define DALL "-|/\\"
global M_Strategy,M_Mvalid # Pluggable procedures
global M_Output # output files
global M_WriteGame # for logger
record morpiongame(grid,score, # the grid & score
Line 68 ⟶ 83:
put(MG.history,M) # save history
MG.score +:= 1 # and score
\M_LogDetails(MG,M)
every x := !M.line do { # draw the line
g := MG.grid[x[1],x[2]]
Line 177 ⟶ 192:
procedure ShowGame(MG) #: show games
if M_Output === &output then
every (\(PrintGrid|WriteMoveLog|M_PrintDetails))(MG)
else # header first to output, game saved
every (\(WriteMoveLog|PrintGrid|M_PrintDetails))(MG)
end
Line 200 ⟶ 215:
/MG.rseed := &random # seed for this game
if MG.move := ?ScanGrid(MG).pool then return MG
end</
===
<
if \M_GameSave then {
savegame := sprintf("Games/%s/%i-L%i",M_GameType,*MG.history,M_Limit)
Line 228 ⟶ 243:
# Date: %s\n# Saved: %s\n# &random: %i\n_
# ReplayFile: %s (%s moves)\n#\n",
\M_GameType|"5T",MG.score,&date,\M_GameSave|"* none *"
MG.rseed,\M_ReplayFile|"* none *",\M_ReplayAfter|"* all *")
end
Line 253 ⟶ 268:
m.line[m.move,2]-m.coff+MG.coff,m.line[m.move,1]-m.roff+MG.roff,
m.direction,(d < 0,"-")|(d = 0,"")|"+",abs(d))
end</
==
None of the code below is needed to satisfy the basic task. It supports the extended framework which includes, command line options, reading and replaying games from a saved file, running mass simulations to glean the best games, and some code for detailed analysis if I ever get around to experimenting with other than random strategy.
===Interface, Parameters, Globals===
<syntaxhighlight lang="unicon">$ifdef EXTENDED
# --- Interface, Parameters, Additional Globals ---
global M_Eval # Pluggable procedure
global M_SrchWid,M_SrchDep # For strategy modules
global M_LogDetails,M_PrintDetails # Misc.
global M_CommandLine,M_Config,M_GameType,M_GameSave
global M_Limit,M_StatUpd,M_BestL,M_WorstL # Multi-game simulation options
global M_ReplayFile,M_ReplayAfter,M_Rseed # For game replay
global
global M_ChartW,M_ChartG # histogram
# --- Beginning of Non-core (Extended) code ---
procedure MorpionConf(A) # Configure the Solver
Line 389 ⟶ 410:
\t-?|-h|-help\tthis help text")
stop()
end</
===
<syntaxhighlight lang="unicon">
procedure MultiMorphion(N,MG) #: Simulate N games using MG
etime := -&time
Line 466 ⟶ 487:
every fprintf(M_Output," %s","-"|®ions) ; fprintf(M_Output,"\n")
fprintf(M_Output,"&storage ( - , - ,string,block) : ")
every fprintf(M_Output," %s","-"|&storage) ; fprintf(M_Output,"\n\n")
fprintf(M_Output,"Icon/Unicon version %s\n",&version)
end </syntaxhighlight>
===
<
Replayer(M := ReadMoveLog(M_ReplayFile)) # read game and save data
M_Strategy := Replayer
Line 521 ⟶ 543:
stop()
}
end</
===
<
fprintf(M_Output,"Reading recorded game from: %s\n",M_ReplayFile)
f := open(M_ReplayFile ,"r") |
Line 574 ⟶ 596:
}
return M
end</
===
<
fprintf(M_Output,"Detailed Move Log\n")
every fprintf(M_Output,"%i : %s\n",i := 1 to *MG.log,MG.log[i])
Line 597 ⟶ 619:
log ||:= sprintf(" Metric=%i",M_Eval(MG)) # append score (opt)
put(MG.log,log) # log the move
end</
===
<
procedure Scorefail(MG);end #: dummy M_Eval always fails
$endif</syntaxhighlight>
{{libheader|Icon Programming Library}}
Line 640 ⟶ 663:
=== Random Game Record ===
The following image was obtained by replaying the game in Pentasol and saving the picture. The original was generated by a multigame simulation and represents the best game generated by this game from the starting position.
[[File:Morpion 5T92 unicon.PNG]]
Line 769 ⟶ 793:
(3,5) / +1
#</pre>
=== Multigame Run ===
The multigame simulation of completely random play includes a histogram showing game scores clustering in the 20's and 60's. This result is similar to results obtained by [http://www.morpionsolitaire.com/English/RecordsGrids5T.htm Jean-Jacques Sibil] (you will have to scroll down that page to find the reference) who has run nearly a billion such simulations achieving a high score of 102 as of 2010.
The following is a summary file:
Line 990 ⟶ 1,013:
®ions ( - , - ,string,block) : - 0 41859440 41859440
&storage ( - , - ,string,block) : - 0 37784 13290772</pre>
== Other Interesting Results ==
One of things I did to get a feel for the game and perhaps get some insight in to strategies was to replay published record games. These universally look smoother and more organized than even the best random games. Somewhere it occurred to me to truncate these record games and play forward randomly to see what happened. I probably expected them to go off the rails fairly quickly. And while that happens, I was surprised how close these could get to the original record. This lead to my earlier observation that the seeds of success are set very early in morpion. It may also be due to the number of possible moves falling off more quickly than I might expect.
* Using Bruneau's 170 game truncated at 112 moves the program produced the following:
<pre>Longest game 168 after 175790 simulations &random=1821730183.
Longest game 169 after 279675 simulations &random=873864083.
Longest game 170 after 1073380 simulations &random=2014543635.
Longest game 170 after 1086106 simulations &random=1319746023.
Results from Sample of 1091265 games of Morpion 5T/D:
Shortest game was 122 moves.
Average game was 127.0640165312733 moves.
Longest game was 170 moves.
Average time/game is 77.48127814967033 ms.
&random is now 609048351.
Summary of Results every '*' = 6761 games
...
115 | ( 0)
120 | (324190) ***********************************************
125 | (540953) ********************************************************************************
130 | (193255) ****************************
135 | ( 17723) **
140 | ( 13447) *
145 | ( 1577)
150 | ( 83)
155 | ( 0)
160 | ( 28)
165 | ( 7)
170 | ( 2) </pre>
: The two games of 170 are both different and not just transpositions. However the difference produced is in a single move.
* Using Rosin's 177 move (A) grid, the program produced the following,
:* from move 129:
<pre>Longest game 145 after 1 simulations.
Longest game 153 after 2 simulations.
Longest game 154 after 20 simulations.
Longest game 155 after 40 simulations.
Longest game 164 after 50 simulations.
Longest game 168 after 2203 simulations.
Results from Sample of 78393 games of Morpion 5T:
Shortest game was 143 moves.
Average game was 147.2826145191535 moves.
Longest game was 168 moves.
Average time/game is 115.6193155001084 ms.
Summary of Results every '*' = 973 games
...
120 | ( 0)
140 | ( 77901) ********************************************************************************
160 | ( 492)</pre>
:* from move 112:
<pre>Longest game 140 after 1 simulations.
Longest game 146 after 10 simulations.
Longest game 148 after 441 simulations.
Longest game 151 after 2029 simulations.
Longest game 153 after 7167 simulations.
Longest game 157 after 34601 simulations.
Longest game 168 after 41977 simulations.
Results from Sample of 524157 games of Morpion 5T:
Shortest game was 126 moves.
Average game was 136.6568528131838 moves.
Longest game was 168 moves.
Average time/game is 138.334270075569 ms.
Summary of Results every '*' = 5643 games
...
100 | ( 0)
120 | (451482) ********************************************************************************
140 | ( 72673) ************
160 | ( 2)</pre>
: Unfortunately that earlier version of the program was not logging the random number seed used for these games nor was it recording games in a notation that I have a converter for (at this time).
The above were run under "Unicon Version 12.0. July 13, 2011" on Windows 7/x64.
| |||