Morpion solitaire/Unicon: Difference between revisions
(introduction) |
(initial code) |
||
Line 17: | Line 17: | ||
* The seeds of success are sown early, as random play from a truncated position in a known good game produces good results |
* The seeds of success are sown early, as random play from a truncated position in a known good game produces good results |
||
* Random play suggests that things are advance fairly quickly before a position gets choked. Many runs hit their mark in the first 5-10k. A few require more (e.g 50K). |
* Random play suggests that things are advance fairly quickly before a position gets choked. Many runs hit their mark in the first 5-10k. A few require more (e.g 50K). |
||
== Core Morpion Routines == |
|||
<lang Unicon>link printf,strings,options |
|||
$define MORPVER "1.7" # version |
|||
procedure main(A) # Morphion |
|||
MorpionConf(A) |
|||
if \M_ReplayFile then ReplayMorpion() |
|||
else if \M_limit === 1 then PlayMorphion5T() |
|||
else MultiSimMorphion(\M_Limit) |
|||
printf("Finished.\n") |
|||
end |
|||
record morpioncell(symbol,direction,row,col) # a grid cell |
|||
record morpionmove(direction,move,line) # move & line |
|||
record morpiongame(grid,log,history,roff,coff,center,pool,move,count) # all game data |
|||
global M_Strategy,M_Eval,M_Mvalid # Pluggable procedures |
|||
global M_CommandLine,M_Config,M_PrintOpt,M_GameSave # Misc. |
|||
global M_Limit,M_StatUpd,M_BestL,M_WorstL # Multi-game simulation options |
|||
global M_SrchWid,M_SrchDep # For strategy modules |
|||
global M_ReplayFile,M_ReplayAfter # For game replay |
|||
$define XEMPTY "." # symbols used in Grid |
|||
$define XINIT "*" |
|||
$define XUSED "+" |
|||
$define DHOR "-" # Directions for moves |
|||
$define DVER "|" |
|||
$define DRD "\\" |
|||
$define DLD "/" |
|||
procedure PlayMorphion5T() #: Play a 5T game |
|||
G := (MG := SetupM5Grid()).grid # start new game |
|||
if M_PrintOpt = 1 then PrintGrid(MG) |
|||
pg := if M_PrintOpt == 2 then PrintGrid else 1 |
|||
while MorphionMove(M_Strategy(pg(MG))) # keep moving |
|||
if M_PrintOpt = 1 then PrintGrid(MG) |
|||
if M_PrintOpt > 0 then { |
|||
PrintLog(MG) |
|||
WriteMoveLog(MG) |
|||
} |
|||
return MG |
|||
end |
|||
procedure MorphionMove(MG) #: make a move |
|||
put(MG.history,M := MG.move) |
|||
log := FormatMoveLog(M,MG.roff,MG.coff) |
|||
log ||:= sprintf(" - of %i choices.",*MG.pool) # append # choices |
|||
log ||:= sprintf(" Metric=%i",M_Eval(MG)) # append score (opt) |
|||
put(MG.log,log) # log the move |
|||
every x := !M.line do { # draw the line |
|||
g := MG.grid[x[1],x[2]] |
|||
g.direction ||:= M.direction |
|||
/g.symbol := XUSED # remove / for all XUSED |
|||
} |
|||
return |
|||
end |
|||
procedure ScanGrid(MG) #: Scan all grid lines |
|||
G := ExpandGrid(MG).grid # expand the grid if needed |
|||
MG.pool := [] # candidate moves |
|||
every c := 1 & r := 1 to *G do # horizontal |
|||
ScanGridLine(G,r,c,0,+1,DHOR,MG.pool) |
|||
every r := 1 & c := 1 to *G[1] do # vertical |
|||
ScanGridLine(G,r,c,+1,0,DVER,MG.pool) |
|||
every ( c := 1 & r := 1 to *G-4 ) | |
|||
( c := 2 to *G[r := 1] ) do # down & right |
|||
ScanGridLine(G,r,c,+1,+1,DRD,MG.pool) |
|||
every ( r := 2 to *G-4 & c := *G[r] ) | |
|||
( c := 5 to *G[r := 1] ) do # down & left |
|||
ScanGridLine(G,r,c,+1,-1,DLD,MG.pool) |
|||
if *MG.history = 0 & M_Strategy ~=== Replayer then { # move 1 special case |
|||
every put(pool1 := [], MG.pool[1|16|28]) # keep i/o corner, o valley |
|||
MG.pool := pool1 |
|||
} |
|||
if *MG.pool > 0 then return MG |
|||
end |
|||
procedure ScanGridLine(G,r0,c0,ri,ci,dir,pool) #: scan 1 grid line (5T) |
|||
local L5,M,r,c,x |
|||
L5 := [] |
|||
r := r0 - ri & c := c0 -ci # one step back |
|||
while put(L5,G[r +:= ri,c +:= ci]) do { |
|||
while *L5 > 5 do pop(L5) # too long ? |
|||
if *L5 < 5 then next # too short ? |
|||
if M_Mvalid(L5,dir) then { # just right, but valid? |
|||
put(pool,M := morpionmove(dir,,[])) # add to pool of valid moves |
|||
every x := L5[i := 1 to *L5] do { |
|||
put(M.line,[x.row,x.col]) |
|||
if /x.symbol then M.move := i |
|||
} |
|||
} |
|||
} |
|||
return pool |
|||
end |
|||
procedure ValidMove5T(L,dir) #: Succeed if L has valid dir move |
|||
local i,j |
|||
if *L ~= 5 then fail # wrong count |
|||
every (i := 0) +:= (/(!L).symbol,1) |
|||
if i ~= 1 then fail # more than 1 avail space |
|||
every (j := 0) +:= ( find(dir,(!L).direction), 1) |
|||
if j > 1 then fail # no overlap, =1 implies at an end |
|||
return # that's it! |
|||
end |
|||
procedure SetupM5Grid() #: construct 5T/D grid & cross |
|||
local G,r,c,s |
|||
every !(G := list(10)) := list(10) # Grid |
|||
every G[r := 1 to 10, c := 1 to 10] := morpioncell(,"",r,c) # Empties |
|||
every s := ![[1,4],[4,1],[4,7],[7,1],[7,7],[10,4]] do { # Cross |
|||
every r := s[1] & c := s[2] + (0 to 3) do |
|||
G[r,c] := morpioncell(XINIT,"",r,c) |
|||
every r := s[2] + (0 to 3) & c := s[1] do |
|||
G[r,c] := morpioncell(XINIT,"",r,c) |
|||
} |
|||
return morpiongame(G,[],[],0,0,1 + (*G-1)/2.) # Create game |
|||
end |
|||
procedure ExpandGrid(MG) #: expand any touching sides |
|||
local r,c,rn,cn,C |
|||
rn := *(G := MG.grid) # capture ... |
|||
cn := *G[1] # ... entry dimensions |
|||
if \(!G)[1].symbol then { # left edge |
|||
MG.coff +:= 1 |
|||
every (cn | (!!G).col) +:= 1 |
|||
every push(G[r := 1 to rn],morpioncell(,"",r,1)) |
|||
} |
|||
if \(!G)[cn].symbol then { # right edge |
|||
cn +:= 1 |
|||
every put(G[r := 1 to rn],morpioncell(,"",r,cn)) |
|||
} |
|||
if \(!G[1]).symbol then { # top edge |
|||
MG.roff +:= 1 |
|||
every (rn | (!!G).row) +:= 1 |
|||
push(G,C := list(cn)) |
|||
every C[c := 1 to cn] := morpioncell(,"",1,c) |
|||
} |
|||
if \(!G[rn]).symbol then { # bottom edge |
|||
rn +:= 1 |
|||
put(G,C := list(cn)) |
|||
every C[c := 1 to cn] := morpioncell(,"",rn,c) |
|||
} |
|||
return MG |
|||
end |
|||
procedure PrintGrid(MG) #: print the current Grid |
|||
G := MG.grid |
|||
write("\nMorphion Solitare Grid (move=",*(L := MG.log),"):\n") |
|||
every (ruler := " ") ||:= (1 to *G[1]) % 10 |
|||
write(ruler) |
|||
every r := 1 to *G do { |
|||
writes(right(r%100,2)," ") |
|||
every c := 1 to *(G[r]) do |
|||
writes(\G[r,c].symbol | XEMPTY) |
|||
write() |
|||
} |
|||
write(ruler,"\n") |
|||
return MG |
|||
end |
|||
procedure PrintLog(MG) #: print the log |
|||
printf("Move Log\n") |
|||
every printf("%i : %s\n",i := 1 to *MG.log,MG.log[i]) |
|||
end |
|||
procedure FormatMoveLog(M,roff,coff) #: format a log entry |
|||
every /(roff|coff) := 0 |
|||
log := sprintf("\"%s\" [%i,%i] : ", |
|||
M.direction,M.line[M.move,1]-roff,M.line[M.move,2]-coff) |
|||
every x := !M.line do |
|||
log ||:= sprintf("[%i,%i] ",x[1]-roff,x[2]-coff) |
|||
return log |
|||
end |
|||
procedure RandomPlayer(MG) #: Simulate random player |
|||
if MG.move := ?ScanGrid(MG).pool then return MG |
|||
end |
|||
procedure Scorefail(MG);end #: dummy always fails</lang> |
|||
== Strategy Support == |
|||
<lang Unicon># Not yet complete </lang> |
|||
== Interface & Parameters == |
|||
<lang Unicon>procedure Usage() |
|||
fprintf(&errout,"_ |
|||
Morphion [options] Plays the 5T variant of Morphion Solitaire\n_ |
|||
Arguments : ") |
|||
every fprintf(&errout," %s",!M_CommandLine) |
|||
fprintf(&errout,"_ |
|||
Morphion [options] Plays the 5T variant of Morphion Solitaire\n_ |
|||
Where options are:\n_ |
|||
\t-P|-print<n>\n_ |
|||
\t\t\tn=2 shows all boards and a log of all moves (every game)\n_ |
|||
\t\t\tn=1 shows a log of the moves and final board (default single game)\n_ |
|||
\t\t\tn=0 produces no per game output (default for multigames)\n_ |
|||
\t-A <a> choose player strategy approach (default=random)\n_ |
|||
\t-SW <n> Search width (strategy dependent)\n_ |
|||
And where these options affect multigame simulations:\n_ |
|||
\t-S <n> runs n games (e.g. -S10) and shows summary of all runs and the board and log for the best result_ |
|||
\t\tnote for larger n this benefits from larger BLKSIZE, STRSIZE environment variables\n_ |
|||
\t-UN <n> Give status update notifications every n simulations\n_ |
|||
\t-B <n> Keep best n games of unique length (default 5)\n_ |
|||
\t-W <n> Keep worst n games of unique length (default 3)\n_ |
|||
\t-R|-replay\treplay\n_ |
|||
\t-RF\tfile containing game record to be replayed\n_ |
|||
\t-RN\tnumber of moves to replay (0=all)\n_ |
|||
\t-E\n_ |
|||
\t-L|-limit\tgames to play (if 0 or less then play until any of 'XxQq' is pressed\n_ |
|||
\t-?|-h|-help\tthis help text") |
|||
stop() |
|||
end |
|||
procedure MorpionConf(A) # Configure the Solver |
|||
M_CommandLine := copy(A) # preserve |
|||
os := "-Q! -L+ -limit+ -P+ -print+ -R! -replay! -RF: -RN+ -save! " |
|||
os ||:= "-UN+ -SW+ -SD+ -A: -E+ -B+ -W+" |
|||
opt := options(A,os,Usage) # -<anything else> gets help |
|||
M_Limit := \opt["limit"|"L"] | 1 |
|||
M_GameSave := opt["save"] |
|||
M_PrintOpt := (0|1|2) = \opt["P"|"print"] |
|||
/M_PrintOpt := \M_Limit === 1 | 0 |
|||
if \opt["R"|"replay"] then { |
|||
M_ReplayFile := \opt["RF"] | "Games/177-5T-rosin.txt" |
|||
M_ReplayAfter := (0 < \opt["RN"]) | &null |
|||
} |
|||
else M_ReplayFile := &null |
|||
M_Strategy := case opt["A"] of { |
|||
"A1" : (def_un := 50, PlayerA1) |
|||
default : (def_un := 500, RandomPlayer) |
|||
} |
|||
M_StatUpd := (0 < \opt["UN"]) | def_un |
|||
M_BestL := (0 < \opt["B"]) | 5 |
|||
M_WorstL := (0 < \opt["W"]) | 0 |
|||
M_SrchWid := (0 < \opt["SW"]) | 5 |
|||
M_SrchDep := (0 < \opt["SD"]) | 5 |
|||
M_Eval := case opt["E"] of { |
|||
"0" : Scorefail |
|||
default : Score1 # also 1 |
|||
} |
|||
c := sprintf("# --- Morpion Solitaire 5 (v%s) ---\n#\n",MORPVER) |
|||
c ||:= "# Command line options :" |
|||
every c ||:= " " || !A |
|||
c ||:= "\n# Summary of Morpion Configuration:\n" |
|||
c ||:= sprintf("# Variant (5T/5D) move validation = %i\n",M_Mvalid := ValidMove5T) |
|||
c ||:= sprintf("# Games to play = %s\n",(0 < M_Limit) | "* unlimited *") |
|||
c ||:= sprintf("# Print (0=none,1=minimal,2=all) = %i\n",M_PrintOpt) |
|||
c ||:= sprintf("# Games will be saved = %s\n",\M_SaveGame) |
|||
c ||:= "# Multi-game options:\n" |
|||
c ||:= sprintf("# - Status Updates = %i\n",M_StatUpd) |
|||
c ||:= sprintf("# - Keep best = %i\n",M_BestL) |
|||
c ||:= sprintf("# - Keep worst = %i\n",M_WorstL) |
|||
c ||:= "# Replaying\n" |
|||
c ||:= sprintf("# - Load recorded game file = %i\n",\M_ReplayFile | "* None *") |
|||
c ||:= sprintf("# - Moves to replay = %i\n",0 ~= \M_ReplayAfter) |
|||
c ||:= sprintf("# Player Strategy = %i\n",M_Strategy) |
|||
c ||:= sprintf("# - Play Evaluator = %i\n",M_Eval) |
|||
c ||:= sprintf("# - Search Width (strategy dependant) = %i\n",M_SrchWid) |
|||
c ||:= sprintf("# - Search Depth (strategy dependant) = %i\n",M_SrchDep) |
|||
c ||:= "#\n# Running:\n" |
|||
M_Config := c |
|||
if \opt["Q"] then stop(M_Config,"-Q Stops run after processing options") |
|||
else write(M_Config) |
|||
end</lang> |
|||
== Multigame Simulation and Monitoring Support == |
|||
<lang Unicon>procedure MultiSimMorphion(N) #: Simulate N games |
|||
etime := -&time |
|||
scores := table(n := 0) |
|||
every bestL|worstL := [] |
|||
if N <= 0 then N := "unlimited" |
|||
repeat { |
|||
if n >= numeric(N) then break else n +:= 1 |
|||
scores[*(mg := PlayMorphion5T()).log] +:= 1 |
|||
mg.count := n # game number |
|||
if short := ( /short | *(\short).log >= *mg.log, mg) then { |
|||
push(worstL,short) # keep worst |
|||
if *worstL > M_WorstL then pull(worstL) |
|||
} |
|||
if long := ( /long | *(\long).log <= *mg.log, mg) then { |
|||
put(bestL,long) # keep best |
|||
if *bestL > M_BestL then get(bestL) |
|||
printf("Longest game %i after %i simulations.\n",*long.log,n) |
|||
fprintf(&errout,"\r%i of %s simulations, long=%i (%s)", |
|||
n,N,*long.log,&dateline) |
|||
} |
|||
if (n % M_StatUpd) = 0 then # show we're alive and working |
|||
fprintf(&errout,"\r%i of %s simulations, long=%i (%s)", |
|||
n,N,*long.log,&dateline) |
|||
if kbhit() & getch() == !"QqXx" then # exit if any q/x |
|||
break fprintf(&errout,"\nExiting after %i simulations.\n",n) |
|||
} |
|||
etime +:= &time |
|||
avg := 0.0 |
|||
short := key(scores) \ 1 # 1 key only |
|||
every i := key(scores) do { # summarize stats |
|||
short >:= i |
|||
avg +:= i * scores[i] |
|||
} |
|||
printf("\nResults from Sample of %i games of Morpion 5T:\n",n) |
|||
printf("Shortest game was %i moves.\n",short) |
|||
printf("Average game was %i moves.\n",avg /:= n) |
|||
printf("Longest game was %i moves.\n",*long.log) |
|||
printf("Average time/game is %i ms.\n",etime/real(n)) |
|||
GraphScores(scores) # graph results |
|||
printf("\nLongest (%i) Game(s):\n",M_BestL) |
|||
every x := !reverse(bestL) do { # show longest game(s) and log |
|||
PrintGrid(x) |
|||
WriteMoveLog(x) |
|||
PrintLog(x) |
|||
} |
|||
printf("\nShortest (%i) Game(s):\n",M_WorstL) |
|||
every x := !worstL do { # show longest game(s) and log |
|||
PrintGrid(x) |
|||
PrintLog(x) |
|||
WriteMoveLog(x) |
|||
} |
|||
MemUsage() # diagnostic |
|||
end |
|||
$define CHARTW 80 # chart width |
|||
$define CHARTG 20 # size of chart buckets |
|||
procedure GraphScores(S) #: graph results |
|||
chart := [] |
|||
every s := key(S) do { # by score |
|||
n := s/CHARTG+1 # chunks of ... |
|||
until chart[n] do put(chart,0) # grow chart to need |
|||
chart[n] +:= S[s] |
|||
} |
|||
s := (1 < max!chart/CHARTW | 1) # scale |
|||
printf("\nSummary of Results every '*' = %d games\n",s) |
|||
every n := 1 to *chart do |
|||
printf("%3d | (%6d) %s\n",(n-1)*CHARTG,chart[n],repl("*",chart[n]/s)) |
|||
end |
|||
procedure MemUsage() #: monitor usage |
|||
printf("\nTotal run time = %i ms\n",&time) |
|||
printf("&allocated (Total,static,string,block) : ") |
|||
every printf(" %i",&allocated) ; printf("\n") |
|||
printf("&collections (Total,static,string,block) : ") |
|||
every printf(" %i",&collections) ; printf("\n") |
|||
printf("®ions ( - , - ,string,block) : ") |
|||
every printf(" %s","-"|®ions) ; printf("\n") |
|||
printf("&storage ( - , - ,string,block) : ") |
|||
every printf(" %s","-"|&storage) ; printf("\n\n") |
|||
end</lang> |
|||
== Game Reloader/Replayer == |
|||
<lang Unicon>procedure ReplayMorpion() #: Handle recorded games |
|||
Replayer(M := ReadMoveLog(M_ReplayFile)) # read game and save data |
|||
if /M_ReplayAfter | (M_ReplayAfter > *M) then { |
|||
printf("Single game replay\n") |
|||
M_Strategy := Replayer |
|||
PlayMorphion5T() |
|||
} |
|||
else { # truncation replay |
|||
G := (MG := SetupM5Grid()).grid # start new grid |
|||
while MorphionMove(Replayer(MG)) do |
|||
if *MG.history = M_ReplayAfter then # play until move |
|||
break |
|||
(SetupM5Grid := ReSetupM5Grid)(MG) # replace procedure and set grid |
|||
if M_Limit === 1 then |
|||
PlayMorphion5T() # single game |
|||
else |
|||
MultiSimMorphion(M_Limit) # simulate many games from here |
|||
} |
|||
return |
|||
end |
|||
procedure ReSetupM5Grid(MG) #: Used to override initial setup |
|||
static MGB |
|||
if MGB := \MG then return # 'set' partial game if arg |
|||
else return deepcopy(MGB) # otherwise return a new copy |
|||
end |
|||
procedure Replayer(MG) #: feed replayed moves |
|||
static ML,radj,cadj |
|||
if type(MG[1]) == "MorpionGameRecord" then return ML := MG |
|||
if not ScanGrid(MG) then fail |
|||
x := get(ML) | fail |
|||
if x.ref = 0 then x := get(ML) | fail |
|||
xr := x.row + MG.roff # adjust for expansion |
|||
xc := x.col + MG.coff |
|||
pool := [] |
|||
every m := !MG.pool do { |
|||
mr := m.line[m.move,1] |
|||
mc := m.line[m.move,2] |
|||
if xr=mr & xc=mc then |
|||
put(pool,m) |
|||
} |
|||
if MG.move := pool[*pool = 1] then # is move unique ? |
|||
return MG |
|||
else # no - need to disambiguate |
|||
if /(x.darow|x.dacol) then { |
|||
printf("Ambiguous position at move #%i with %i choices\n_ |
|||
Need unique disambiguation, syntax: n:r,c^r,c\n",*MG.log+1,*pool) |
|||
every m := !pool do |
|||
printf(" %s\n",FormatMoveLog(m,MG.roff,MG.coff)) |
|||
} |
|||
else { |
|||
dr := x.darow + MG.roff # adjust for expansion |
|||
dc := x.dacol + MG.coff |
|||
every p := ((m := !pool).line)[1|5] do |
|||
if p[1] = dr & p[2] = dc then { |
|||
MG.move := m |
|||
return MG |
|||
} |
|||
printf("No Match found to disambiguate move #%i\n",*MG.log+1) |
|||
every m := !pool do |
|||
printf(" %s\n",FormatMoveLog(m,MG.roff,MG.coff)) |
|||
} |
|||
PrintGrid(MG) |
|||
PrintLog(MG) |
|||
WriteMoveLog(MG) |
|||
stop() |
|||
end |
|||
record MorpionGameRecord(ref,row,col,darow,dacol) |
|||
procedure ReadMoveLog(fn) #: Read a move log |
|||
printf("Reading recorded game from: %s\n",fn) |
|||
f := open(fn,"r") | stop("Unable to open file ",fn," for read.") |
|||
M := [] |
|||
while b := trim(read(f)) do { |
|||
if b ? ="$end" then break # allow pre-mature end of file |
|||
b := deletec(b,' \t') |
|||
b ?:= tab(find("#")|0) |
|||
until *b = 0 do { |
|||
x := MorpionGameRecord() |
|||
b ?:= ( x.ref := integer(tab(many(&digits))),=":", # base |
|||
x.row := integer(=!["-","+",""]||tab(many(&digits))),=",", |
|||
x.col := integer(=!["-","+",""]||tab(many(&digits))), |
|||
tab(0)) | |
|||
stop(&output,"Syntax error in line above.") |
|||
if b ?:= ( ="^", tab(0)) then { # disamb |
|||
b ?:= ( x.darow := integer(=!["-","+",""]||tab(many(&digits))),=",", |
|||
x.dacol := integer(=!["-","+",""]||tab(many(&digits))), |
|||
tab(0)) | |
|||
stop(&output,"Syntax error in line above (disamiguation).") |
|||
} |
|||
b ?:= ( =(";"|""), tab(0) ) |
|||
put(M,x) |
|||
} |
|||
} |
|||
return sortf(M,1) |
|||
end |
|||
procedure WriteMoveLog(MG) #: write out a re-readable move log |
|||
savegame := sprintf("Games/%i-L%i",*MG.history,M_Limit) |
|||
if M_Limit ~= 1 then |
|||
savegame ||:= sprintf("(%i)",MG.count) |
|||
if \M_ReplayFile then { |
|||
M_ReplayFile ? (="Games/", savegame ||:= "-RF" || tab(find(".txt"))) |
|||
savegame ||:= "-RN" || (0 < M_ReplayAfter) |
|||
} |
|||
savegame ||:= sprintf("_%s-%s.txt",deletec(&date,'/'),deletec(&clock,':')) |
|||
c := sprintf( "#\n# Game Record for Morphion 5T game of %i moves\n_ |
|||
# Reference: %s\n_ |
|||
# Syntax for recorded games:\n_ |
|||
# 1. whitespace and comments (everything past #) are ignored\n_ |
|||
# 2. moves may be ; or newline separated\n_ |
|||
# 3. moves are formatted (using BNF style variables like <x>):\n_ |
|||
# <movenumber>:<row>,<col>[^<drow>,<dcol>]\n_ |
|||
# The optional drow/dcol values provide an additional point\n_ |
|||
# used to disambiguate moves. The point drow/dcol must be\n_ |
|||
# chosen at one end of the line.\n_ |
|||
# Moves are applied in sorted order.\n_ |
|||
# 4. all row/col coordinates are relative to the 1,1 origin\n_ |
|||
# located at the intersection of the lines containing the\n_ |
|||
# top and left most edges of the cross.\n#\n",*MG.history,savegame) |
|||
every m := MG.history[i := 1 to *MG.history] do { |
|||
e := m.move ~= (1|5) |
|||
/l := "" |
|||
l ||:= sprintf("%i:%i,%i^%i,%i;", |
|||
i,m.line[m.move,1],m.line[m.move,2],m.line[e,1],m.line[e,2]) |
|||
if *l > 70 then { |
|||
c ||:= l || "\n" |
|||
l := &null |
|||
} |
|||
} |
|||
c ||:= \l || "\n" |
|||
write(c) |
|||
if \M_GameSave then { |
|||
f := open(savegame,"w") | stop("Unable to open ",savegame," for writing") |
|||
write(f,M_Config,c) |
|||
close(f) |
|||
} |
|||
end</lang> |
|||
{{libheader|Icon Programming Library}} |
|||
[http://www.cs.arizona.edu/icon/library/src/procs/printf.icn printf.icn provides formatting] |
|||
[http://www.cs.arizona.edu/icon/library/src/procs/strings.icn strings.icn provides deletec] |
|||
[http://www.cs.arizona.edu/icon/library/src/procs/options.icn options.icn provides options processing] |
|||
<br/>'''Other RosettaCode pages used''' [[DeepCopy]] |
|||
SampleOutput:<pre>TBD</pre> |
Revision as of 21:50, 4 February 2012
Using random play in many summary runs, the highest score achieved was 90. 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 will require some very long runs and is unlikely to result in any significant progress.
The program is structured to allow its behaviour to be configured (see M_ vars) to do multi-game simulations and try out strategies. It was a first cut/test bed designed more to understand and explore the problem space rather than for high efficiency.
The grid is automatically expanded as needed whenever a cell is played on an outer edge. When this happens only the affected side is expanded. As a side effect the grid numbering will seem unusual. The game log shows all row/col coordinates relative to the 1,1 origin located at the intersection of the lines containing top and left most edges of the cross.
Extensions/features include:
- Play single games or run multigame simulations to find and capture the best games
- Read/write a game record and ability to replay a game to the end or to a specific move
- Save a game
- Use a plugable scoring/evaluation procedure at each move (for heuristics)
- Limit initial random moves to 1 of 3 cases (inside/outside corner, outside valley) not 1 of 28
For more see: Morpion -h|-help
Observations:
- The seeds of success are sown early, as random play from a truncated position in a known good game produces good results
- Random play suggests that things are advance fairly quickly before a position gets choked. Many runs hit their mark in the first 5-10k. A few require more (e.g 50K).
Core Morpion Routines
<lang Unicon>link printf,strings,options
$define MORPVER "1.7" # version
procedure main(A) # Morphion
MorpionConf(A) if \M_ReplayFile then ReplayMorpion() else if \M_limit === 1 then PlayMorphion5T() else MultiSimMorphion(\M_Limit) printf("Finished.\n")
end
record morpioncell(symbol,direction,row,col) # a grid cell record morpionmove(direction,move,line) # move & line record morpiongame(grid,log,history,roff,coff,center,pool,move,count) # all game data
global M_Strategy,M_Eval,M_Mvalid # Pluggable procedures global M_CommandLine,M_Config,M_PrintOpt,M_GameSave # Misc. global M_Limit,M_StatUpd,M_BestL,M_WorstL # Multi-game simulation options global M_SrchWid,M_SrchDep # For strategy modules global M_ReplayFile,M_ReplayAfter # For game replay
$define XEMPTY "." # symbols used in Grid $define XINIT "*" $define XUSED "+"
$define DHOR "-" # Directions for moves $define DVER "|" $define DRD "\\" $define DLD "/"
procedure PlayMorphion5T() #: Play a 5T game
G := (MG := SetupM5Grid()).grid # start new game if M_PrintOpt = 1 then PrintGrid(MG) pg := if M_PrintOpt == 2 then PrintGrid else 1 while MorphionMove(M_Strategy(pg(MG))) # keep moving if M_PrintOpt = 1 then PrintGrid(MG) if M_PrintOpt > 0 then { PrintLog(MG) WriteMoveLog(MG) } return MG
end
procedure MorphionMove(MG) #: make a move
put(MG.history,M := MG.move) log := FormatMoveLog(M,MG.roff,MG.coff) log ||:= sprintf(" - of %i choices.",*MG.pool) # append # choices log ||:= sprintf(" Metric=%i",M_Eval(MG)) # append score (opt) put(MG.log,log) # log the move every x := !M.line do { # draw the line g := MG.grid[x[1],x[2]] g.direction ||:= M.direction /g.symbol := XUSED # remove / for all XUSED } return
end
procedure ScanGrid(MG) #: Scan all grid lines
G := ExpandGrid(MG).grid # expand the grid if needed MG.pool := [] # candidate moves every c := 1 & r := 1 to *G do # horizontal ScanGridLine(G,r,c,0,+1,DHOR,MG.pool) every r := 1 & c := 1 to *G[1] do # vertical ScanGridLine(G,r,c,+1,0,DVER,MG.pool) every ( c := 1 & r := 1 to *G-4 ) | ( c := 2 to *G[r := 1] ) do # down & right ScanGridLine(G,r,c,+1,+1,DRD,MG.pool) every ( r := 2 to *G-4 & c := *G[r] ) | ( c := 5 to *G[r := 1] ) do # down & left ScanGridLine(G,r,c,+1,-1,DLD,MG.pool)
if *MG.history = 0 & M_Strategy ~=== Replayer then { # move 1 special case every put(pool1 := [], MG.pool[1|16|28]) # keep i/o corner, o valley MG.pool := pool1 } if *MG.pool > 0 then return MG
end
procedure ScanGridLine(G,r0,c0,ri,ci,dir,pool) #: scan 1 grid line (5T)
local L5,M,r,c,x L5 := [] r := r0 - ri & c := c0 -ci # one step back while put(L5,G[r +:= ri,c +:= ci]) do { while *L5 > 5 do pop(L5) # too long ? if *L5 < 5 then next # too short ? if M_Mvalid(L5,dir) then { # just right, but valid? put(pool,M := morpionmove(dir,,[])) # add to pool of valid moves every x := L5[i := 1 to *L5] do { put(M.line,[x.row,x.col]) if /x.symbol then M.move := i } } } return pool
end
procedure ValidMove5T(L,dir) #: Succeed if L has valid dir move
local i,j if *L ~= 5 then fail # wrong count every (i := 0) +:= (/(!L).symbol,1) if i ~= 1 then fail # more than 1 avail space every (j := 0) +:= ( find(dir,(!L).direction), 1) if j > 1 then fail # no overlap, =1 implies at an end return # that's it!
end
procedure SetupM5Grid() #: construct 5T/D grid & cross
local G,r,c,s every !(G := list(10)) := list(10) # Grid every G[r := 1 to 10, c := 1 to 10] := morpioncell(,"",r,c) # Empties every s := ![[1,4],[4,1],[4,7],[7,1],[7,7],[10,4]] do { # Cross every r := s[1] & c := s[2] + (0 to 3) do G[r,c] := morpioncell(XINIT,"",r,c) every r := s[2] + (0 to 3) & c := s[1] do G[r,c] := morpioncell(XINIT,"",r,c) } return morpiongame(G,[],[],0,0,1 + (*G-1)/2.) # Create game
end
procedure ExpandGrid(MG) #: expand any touching sides
local r,c,rn,cn,C rn := *(G := MG.grid) # capture ... cn := *G[1] # ... entry dimensions if \(!G)[1].symbol then { # left edge MG.coff +:= 1 every (cn | (!!G).col) +:= 1 every push(G[r := 1 to rn],morpioncell(,"",r,1)) } if \(!G)[cn].symbol then { # right edge cn +:= 1 every put(G[r := 1 to rn],morpioncell(,"",r,cn)) } if \(!G[1]).symbol then { # top edge MG.roff +:= 1 every (rn | (!!G).row) +:= 1 push(G,C := list(cn)) every C[c := 1 to cn] := morpioncell(,"",1,c) } if \(!G[rn]).symbol then { # bottom edge rn +:= 1 put(G,C := list(cn)) every C[c := 1 to cn] := morpioncell(,"",rn,c) } return MG
end
procedure PrintGrid(MG) #: print the current Grid
G := MG.grid write("\nMorphion Solitare Grid (move=",*(L := MG.log),"):\n") every (ruler := " ") ||:= (1 to *G[1]) % 10 write(ruler) every r := 1 to *G do { writes(right(r%100,2)," ") every c := 1 to *(G[r]) do writes(\G[r,c].symbol | XEMPTY) write() } write(ruler,"\n") return MG
end
procedure PrintLog(MG) #: print the log
printf("Move Log\n") every printf("%i : %s\n",i := 1 to *MG.log,MG.log[i])
end
procedure FormatMoveLog(M,roff,coff) #: format a log entry
every /(roff|coff) := 0 log := sprintf("\"%s\" [%i,%i] : ", M.direction,M.line[M.move,1]-roff,M.line[M.move,2]-coff) every x := !M.line do log ||:= sprintf("[%i,%i] ",x[1]-roff,x[2]-coff) return log
end
procedure RandomPlayer(MG) #: Simulate random player
if MG.move := ?ScanGrid(MG).pool then return MG
end
procedure Scorefail(MG);end #: dummy always fails</lang>
Strategy Support
<lang Unicon># Not yet complete </lang>
Interface & Parameters
<lang Unicon>procedure Usage()
fprintf(&errout,"_ Morphion [options] Plays the 5T variant of Morphion Solitaire\n_ Arguments : ") every fprintf(&errout," %s",!M_CommandLine) fprintf(&errout,"_ Morphion [options] Plays the 5T variant of Morphion Solitaire\n_ Where options are:\n_ \t-P|-print<n>\n_ \t\t\tn=2 shows all boards and a log of all moves (every game)\n_ \t\t\tn=1 shows a log of the moves and final board (default single game)\n_ \t\t\tn=0 produces no per game output (default for multigames)\n_ \t-A <a> choose player strategy approach (default=random)\n_ \t-SW <n> Search width (strategy dependent)\n_ And where these options affect multigame simulations:\n_ \t-S <n> runs n games (e.g. -S10) and shows summary of all runs and the board and log for the best result_ \t\tnote for larger n this benefits from larger BLKSIZE, STRSIZE environment variables\n_ \t-UN <n> Give status update notifications every n simulations\n_ \t-B <n> Keep best n games of unique length (default 5)\n_ \t-W <n> Keep worst n games of unique length (default 3)\n_ \t-R|-replay\treplay\n_ \t-RF\tfile containing game record to be replayed\n_ \t-RN\tnumber of moves to replay (0=all)\n_ \t-E\n_ \t-L|-limit\tgames to play (if 0 or less then play until any of 'XxQq' is pressed\n_ \t-?|-h|-help\tthis help text") stop()
end
procedure MorpionConf(A) # Configure the Solver
M_CommandLine := copy(A) # preserve os := "-Q! -L+ -limit+ -P+ -print+ -R! -replay! -RF: -RN+ -save! " os ||:= "-UN+ -SW+ -SD+ -A: -E+ -B+ -W+" opt := options(A,os,Usage) # -<anything else> gets help M_Limit := \opt["limit"|"L"] | 1 M_GameSave := opt["save"] M_PrintOpt := (0|1|2) = \opt["P"|"print"] /M_PrintOpt := \M_Limit === 1 | 0 if \opt["R"|"replay"] then { M_ReplayFile := \opt["RF"] | "Games/177-5T-rosin.txt" M_ReplayAfter := (0 < \opt["RN"]) | &null } else M_ReplayFile := &null M_Strategy := case opt["A"] of { "A1" : (def_un := 50, PlayerA1) default : (def_un := 500, RandomPlayer) } M_StatUpd := (0 < \opt["UN"]) | def_un M_BestL := (0 < \opt["B"]) | 5 M_WorstL := (0 < \opt["W"]) | 0 M_SrchWid := (0 < \opt["SW"]) | 5 M_SrchDep := (0 < \opt["SD"]) | 5 M_Eval := case opt["E"] of { "0" : Scorefail default : Score1 # also 1 } c := sprintf("# --- Morpion Solitaire 5 (v%s) ---\n#\n",MORPVER) c ||:= "# Command line options :" every c ||:= " " || !A c ||:= "\n# Summary of Morpion Configuration:\n" c ||:= sprintf("# Variant (5T/5D) move validation = %i\n",M_Mvalid := ValidMove5T) c ||:= sprintf("# Games to play = %s\n",(0 < M_Limit) | "* unlimited *") c ||:= sprintf("# Print (0=none,1=minimal,2=all) = %i\n",M_PrintOpt) c ||:= sprintf("# Games will be saved = %s\n",\M_SaveGame) c ||:= "# Multi-game options:\n" c ||:= sprintf("# - Status Updates = %i\n",M_StatUpd) c ||:= sprintf("# - Keep best = %i\n",M_BestL) c ||:= sprintf("# - Keep worst = %i\n",M_WorstL) c ||:= "# Replaying\n" c ||:= sprintf("# - Load recorded game file = %i\n",\M_ReplayFile | "* None *") c ||:= sprintf("# - Moves to replay = %i\n",0 ~= \M_ReplayAfter) c ||:= sprintf("# Player Strategy = %i\n",M_Strategy) c ||:= sprintf("# - Play Evaluator = %i\n",M_Eval) c ||:= sprintf("# - Search Width (strategy dependant) = %i\n",M_SrchWid) c ||:= sprintf("# - Search Depth (strategy dependant) = %i\n",M_SrchDep) c ||:= "#\n# Running:\n" M_Config := c if \opt["Q"] then stop(M_Config,"-Q Stops run after processing options") else write(M_Config)
end</lang>
Multigame Simulation and Monitoring Support
<lang Unicon>procedure MultiSimMorphion(N) #: Simulate N games
etime := -&time scores := table(n := 0) every bestL|worstL := [] if N <= 0 then N := "unlimited" repeat { if n >= numeric(N) then break else n +:= 1 scores[*(mg := PlayMorphion5T()).log] +:= 1 mg.count := n # game number if short := ( /short | *(\short).log >= *mg.log, mg) then { push(worstL,short) # keep worst if *worstL > M_WorstL then pull(worstL) } if long := ( /long | *(\long).log <= *mg.log, mg) then { put(bestL,long) # keep best if *bestL > M_BestL then get(bestL) printf("Longest game %i after %i simulations.\n",*long.log,n) fprintf(&errout,"\r%i of %s simulations, long=%i (%s)", n,N,*long.log,&dateline) } if (n % M_StatUpd) = 0 then # show we're alive and working fprintf(&errout,"\r%i of %s simulations, long=%i (%s)", n,N,*long.log,&dateline) if kbhit() & getch() == !"QqXx" then # exit if any q/x break fprintf(&errout,"\nExiting after %i simulations.\n",n) } etime +:= &time avg := 0.0 short := key(scores) \ 1 # 1 key only every i := key(scores) do { # summarize stats short >:= i avg +:= i * scores[i] } printf("\nResults from Sample of %i games of Morpion 5T:\n",n) printf("Shortest game was %i moves.\n",short) printf("Average game was %i moves.\n",avg /:= n) printf("Longest game was %i moves.\n",*long.log) printf("Average time/game is %i ms.\n",etime/real(n)) GraphScores(scores) # graph results printf("\nLongest (%i) Game(s):\n",M_BestL) every x := !reverse(bestL) do { # show longest game(s) and log PrintGrid(x) WriteMoveLog(x) PrintLog(x) } printf("\nShortest (%i) Game(s):\n",M_WorstL) every x := !worstL do { # show longest game(s) and log PrintGrid(x) PrintLog(x) WriteMoveLog(x) } MemUsage() # diagnostic
end
$define CHARTW 80 # chart width $define CHARTG 20 # size of chart buckets
procedure GraphScores(S) #: graph results
chart := [] every s := key(S) do { # by score n := s/CHARTG+1 # chunks of ... until chart[n] do put(chart,0) # grow chart to need chart[n] +:= S[s] } s := (1 < max!chart/CHARTW | 1) # scale printf("\nSummary of Results every '*' = %d games\n",s) every n := 1 to *chart do printf("%3d | (%6d) %s\n",(n-1)*CHARTG,chart[n],repl("*",chart[n]/s))
end
procedure MemUsage() #: monitor usage
printf("\nTotal run time = %i ms\n",&time) printf("&allocated (Total,static,string,block) : ") every printf(" %i",&allocated) ; printf("\n") printf("&collections (Total,static,string,block) : ") every printf(" %i",&collections) ; printf("\n") printf("®ions ( - , - ,string,block) : ") every printf(" %s","-"|®ions) ; printf("\n") printf("&storage ( - , - ,string,block) : ") every printf(" %s","-"|&storage) ; printf("\n\n")
end</lang>
Game Reloader/Replayer
<lang Unicon>procedure ReplayMorpion() #: Handle recorded games
Replayer(M := ReadMoveLog(M_ReplayFile)) # read game and save data if /M_ReplayAfter | (M_ReplayAfter > *M) then { printf("Single game replay\n") M_Strategy := Replayer PlayMorphion5T() } else { # truncation replay G := (MG := SetupM5Grid()).grid # start new grid while MorphionMove(Replayer(MG)) do if *MG.history = M_ReplayAfter then # play until move break (SetupM5Grid := ReSetupM5Grid)(MG) # replace procedure and set grid if M_Limit === 1 then PlayMorphion5T() # single game else MultiSimMorphion(M_Limit) # simulate many games from here } return
end
procedure ReSetupM5Grid(MG) #: Used to override initial setup
static MGB if MGB := \MG then return # 'set' partial game if arg else return deepcopy(MGB) # otherwise return a new copy
end
procedure Replayer(MG) #: feed replayed moves static ML,radj,cadj
if type(MG[1]) == "MorpionGameRecord" then return ML := MG if not ScanGrid(MG) then fail x := get(ML) | fail if x.ref = 0 then x := get(ML) | fail xr := x.row + MG.roff # adjust for expansion xc := x.col + MG.coff pool := [] every m := !MG.pool do { mr := m.line[m.move,1] mc := m.line[m.move,2] if xr=mr & xc=mc then put(pool,m) } if MG.move := pool[*pool = 1] then # is move unique ? return MG else # no - need to disambiguate if /(x.darow|x.dacol) then { printf("Ambiguous position at move #%i with %i choices\n_ Need unique disambiguation, syntax: n:r,c^r,c\n",*MG.log+1,*pool) every m := !pool do printf(" %s\n",FormatMoveLog(m,MG.roff,MG.coff)) } else { dr := x.darow + MG.roff # adjust for expansion dc := x.dacol + MG.coff every p := ((m := !pool).line)[1|5] do if p[1] = dr & p[2] = dc then { MG.move := m return MG } printf("No Match found to disambiguate move #%i\n",*MG.log+1) every m := !pool do printf(" %s\n",FormatMoveLog(m,MG.roff,MG.coff)) } PrintGrid(MG) PrintLog(MG) WriteMoveLog(MG) stop()
end
record MorpionGameRecord(ref,row,col,darow,dacol)
procedure ReadMoveLog(fn) #: Read a move log
printf("Reading recorded game from: %s\n",fn) f := open(fn,"r") | stop("Unable to open file ",fn," for read.") M := [] while b := trim(read(f)) do { if b ? ="$end" then break # allow pre-mature end of file b := deletec(b,' \t') b ?:= tab(find("#")|0) until *b = 0 do { x := MorpionGameRecord() b ?:= ( x.ref := integer(tab(many(&digits))),=":", # base x.row := integer(=!["-","+",""]||tab(many(&digits))),=",", x.col := integer(=!["-","+",""]||tab(many(&digits))), tab(0)) | stop(&output,"Syntax error in line above.") if b ?:= ( ="^", tab(0)) then { # disamb b ?:= ( x.darow := integer(=!["-","+",""]||tab(many(&digits))),=",", x.dacol := integer(=!["-","+",""]||tab(many(&digits))), tab(0)) | stop(&output,"Syntax error in line above (disamiguation).") } b ?:= ( =(";"|""), tab(0) ) put(M,x) } } return sortf(M,1)
end
procedure WriteMoveLog(MG) #: write out a re-readable move log
savegame := sprintf("Games/%i-L%i",*MG.history,M_Limit) if M_Limit ~= 1 then savegame ||:= sprintf("(%i)",MG.count) if \M_ReplayFile then { M_ReplayFile ? (="Games/", savegame ||:= "-RF" || tab(find(".txt"))) savegame ||:= "-RN" || (0 < M_ReplayAfter) } savegame ||:= sprintf("_%s-%s.txt",deletec(&date,'/'),deletec(&clock,':')) c := sprintf( "#\n# Game Record for Morphion 5T game of %i moves\n_ # Reference: %s\n_ # Syntax for recorded games:\n_ # 1. whitespace and comments (everything past #) are ignored\n_ # 2. moves may be ; or newline separated\n_ # 3. moves are formatted (using BNF style variables like <x>):\n_ # <movenumber>:<row>,<col>[^<drow>,<dcol>]\n_ # The optional drow/dcol values provide an additional point\n_ # used to disambiguate moves. The point drow/dcol must be\n_ # chosen at one end of the line.\n_ # Moves are applied in sorted order.\n_ # 4. all row/col coordinates are relative to the 1,1 origin\n_ # located at the intersection of the lines containing the\n_ # top and left most edges of the cross.\n#\n",*MG.history,savegame) every m := MG.history[i := 1 to *MG.history] do { e := m.move ~= (1|5) /l := "" l ||:= sprintf("%i:%i,%i^%i,%i;", i,m.line[m.move,1],m.line[m.move,2],m.line[e,1],m.line[e,2]) if *l > 70 then { c ||:= l || "\n" l := &null } } c ||:= \l || "\n" write(c) if \M_GameSave then { f := open(savegame,"w") | stop("Unable to open ",savegame," for writing") write(f,M_Config,c) close(f) }
end</lang>
printf.icn provides formatting
strings.icn provides deletec
options.icn provides options processing
Other RosettaCode pages used DeepCopy
SampleOutput:
TBD