Morpion solitaire
Task Requirements
The task is to get the computer to play a game of Morpion solitaire. For this task, it is acceptable for the computer to make randomly selected valid moves, rather than playing the strongest move each time. Use the standard version, with 5 point lines that allows parallel lines to touch at the endpoints.
(Proposed additional requirement): Provide sample output. Preferably the output should be a record of moves suitable for replay using Pentasol. Alternately, ASCII art can be used; however, games rendered in this manner may not provide enough information to replay the game. Please see the discussion on game notation and rendering for more information.
Playing Morpion Solitaire
There are several variations of the game, this task deals with the 5 point "touching" version also known as "5T".
Morpian solitaire is played on a (theoretically) infinite grid. It begins with 36 points marked in a Greek cross:
...XXXX... ...X..X... ...X..X... XXXX..XXXX X........X X........X XXXX..XXXX ...X..X... ...X..X... ...XXXX...
- A move is made by adding one point anywhere that creates a new line of 5 points (without spaces) and drawing a line through them. (Moves are commonly marked with the number of the move for visual clarity. Creating a record of the game in game notation is a better way to validate a game.)
- Any two lines not running in the same direction may cross.
- Any two lines running in the same direction are allowed to touch at the ends but not overlap (i.e. share at most a single point).
- The game ends when you run out of legal moves. (The game score is the number of legal moves played.)
The rules to morpion solitaire are here.
Background
A short history of the 5T game:
- 170 - Bruneau, by hand in 1976
- 117 and 122 - Juillé in 1995 and 1999
- 143 - Zimmer in 2003
- 144 - Cazenave in 2007
- 172 - Rosin in 2010
- 171 and 172 - Tishchenko in 2011
- 177 and 178 - Rosin in 2011
For an up to date list of Morpion 5T Records see here. The shortest game possible is 20 moves.
The game is NP-hard in the general case and has a huge search space and is a test case for research into searching methods.
Theoretical bounds have been placed on the longest 5T game. The lower bound of 170 and upper bound of either 324 or 704 according to two different papers (see talk page).
C
Console play with ncurses. Length and touching rules can be changed at the begining of source code. 'q' key to quit, space key to toggle auto move, anykey for next move. Play is random. I got nowhere near the record 177 moves, but did approach the worst-possible (20) quite often. <lang C>#include <ncurses.h>
- include <stdlib.h>
- include <unistd.h>
- include <time.h>
/* option: how long a line is. Options probably should have been made into
- commandline args, if I were not lazy. Also, if line_len is set to 3,
- the game may keep going indefinitely: best use auto mode. */
int line_len = 5;
/* option: whether two lines are allowed to be in the same direction and
- connected end to end. Note: two lines crossing are always ok. */
int disjoint = 0;
int **board = 0, width, height;
- define for_i for(i = 0; i < height; i++)
- define for_j for(j = 0; j < width; j++)
enum { s_blank = 0, s_occupied = 1 << 0, s_dir_ns = 1 << 1, s_dir_ew = 1 << 2, s_dir_ne_sw = 1 << 3, s_dir_nw_se = 1 << 4, s_newly_added = 1 << 5, s_current = 1 << 6, };
int irand(int n) { int r, rand_max = RAND_MAX - (RAND_MAX % n); while ((r = rand()) >= rand_max); return r / (rand_max / n); }
int** alloc_board(int w, int h) { int i; int **buf = calloc(1, sizeof(int *) * h + sizeof(int) * h * w);
buf[0] = (int*)(buf + h); for (i = 1; i < h; i++) buf[i] = buf[i - 1] + w; return buf; }
/* -1: expand low index end; 1: exten high index end */ void expand_board(int dw, int dh) { int i, j; int nw = width + !!dw, nh = height + !!dh;
/* garanteed to fragment heap: not realloc because copying elements * is a bit tricky */ int **nbuf = alloc_board(nw, nh);
dw = -(dw < 0), dh = -(dh < 0);
for (i = 0; i < nh; i++) { if (i + dh < 0 || i + dh >= height) continue; for (j = 0; j < nw; j++) { if (j + dw < 0 || j + dw >= width) continue; nbuf[i][j] = board[i + dh][j + dw]; } } free(board);
board = nbuf; width = nw; height = nh; }
void array_set(int **buf, int v, int x0, int y0, int x1, int y1) { int i, j; for (i = y0; i <= y1; i++) for (j = x0; j <= x1; j++) buf[i][j] = v; }
void show_board() { int i, j; for_i for_j mvprintw(i + 1, j * 2, (board[i][j] & s_current) ? "X " : (board[i][j] & s_newly_added) ? "O " : (board[i][j] & s_occupied) ? "+ " : " "); refresh(); }
void init_board() { width = height = 3 * (line_len - 1); board = alloc_board(width, height);
array_set(board, s_occupied, line_len - 1, 1, 2 * line_len - 3, height - 2); array_set(board, s_occupied, 1, line_len - 1, width - 2, 2 * line_len - 3);
array_set(board, s_blank, line_len, 2, 2 * line_len - 4, height - 3); array_set(board, s_blank, 2, line_len, width - 3, 2 * line_len - 4); }
int ofs[4][3] = { {0, 1, s_dir_ns}, {1, 0, s_dir_ew}, {1, -1, s_dir_ne_sw}, {1, 1, s_dir_nw_se} };
typedef struct { int m, s, seq, x, y; } move_t;
/* test if a point can complete a line, or take that point */ void test_postion(int y, int x, move_t * rec) { int m, k, s, dx, dy, xx, yy, dir; if (board[y][x] & s_occupied) return;
for (m = 0; m < 4; m++) { /* 4 directions */ dx = ofs[m][0]; dy = ofs[m][1]; dir = ofs[m][2];
for (s = 1 - line_len; s <= 0; s++) { /* offset line */ for (k = 0; k < line_len; k++) { if (s + k == 0) continue;
xx = x + dx * (s + k); yy = y + dy * (s + k); if (xx < 0 || xx >= width || yy < 0 || yy >= height) break;
/* no piece at position */ if (!(board[yy][xx] & s_occupied)) break;
/* this direction taken */ if ((board[yy][xx] & dir)) break; } if (k != line_len) continue;
/* position ok; irand() to even each option's chance of being picked */ if (! irand(++rec->seq)) rec->m = m, rec->s = s, rec->x = x, rec->y = y; } } }
void add_piece(move_t *rec) { int dx = ofs[rec->m][0]; int dy = ofs[rec->m][1]; int dir= ofs[rec->m][2]; int xx, yy, k;
board[rec->y][rec->x] |= (s_current | s_occupied);
for (k = 0; k < line_len; k++) { xx = rec->x + dx * (k + rec->s); yy = rec->y + dy * (k + rec->s); board[yy][xx] |= s_newly_added; if (k >= disjoint || k < line_len - disjoint) board[yy][xx] |= dir; } }
int next_move() { int i, j; move_t rec; rec.seq = 0;
/* wipe last iteration's new line markers */ for_i for_j board[i][j] &= ~(s_newly_added | s_current);
/* randomly pick one of next legal moves */ for_i for_j test_postion(i, j, &rec);
/* didn't find any move, game over */ if (!rec.seq) return 0;
add_piece(&rec);
rec.x = (rec.x == width - 1) ? 1 : rec.x ? 0 : -1; rec.y = (rec.y == height - 1) ? 1 : rec.y ? 0 : -1;
if (rec.x || rec.y) expand_board(rec.x, rec.y); return 1; }
int main() { int ch = 0; int move = 0; int wait_key = 1;
init_board(); srand(time(0));
initscr(); noecho(); cbreak();
do { mvprintw(0, 0, "Move %d", move++); show_board(); if (!next_move()) { next_move(); show_board(); break; } if (!wait_key) usleep(100000); if ((ch = getch()) == ' ') { wait_key = !wait_key; if (wait_key) timeout(-1); else timeout(0); } } while (ch != 'q');
timeout(-1); nocbreak(); echo();
endwin(); return 0; }</lang>
Icon and Unicon
The example provided goes beyond the basic requirement to play out a random game. It provides a flexible framework to explore the challenge of morpion solitaire.
Java
REXX
This REXX program is an attempt to play (badly, and with random moves) the game of Morpion solitaire by a computer.
The program also allows a carbon-based life form (er, that is, a human) to play.
This is a work in progress and currently doesn't log the moves in the manner asked for by this task.
The moves are marked by 0123456789ABC...XYZabc...xyz()[]{}<>«» and thereafter by a plus sign (+) on the board which is shown in 2D.
This allows 73 unique moves to be shown on the board (or grid), but all moves are also logged to a file.
Currently, the computer tries to start the game (with sixteen moves) by the assumptions I made, which clearly aren't worth a tinker's dam.
This program allows the D or T forms of the game, and allows any board size (grid size) of three or higher.
The default games is 5T
<lang rexx>/*REXX program to play Morpion solitaire, the default is the 5T version.*/ signal on syntax; signal on novalue /*handle REXX program errors. */ quiet=0; oFID='MORPION' arg game player . /*see if a person wants to play. */ if game== | game==',' then game='5T' /*Not specified? Then use default*/ prompt= /*null string is used for ERR ret*/ TorD='T (touching) ───or─── D (disjoint).' /*valid games types (T | D).*/ gT=right(game,1) /*T = touching ─or─ D = disjoint.*/ if \datatype(gT,'U') | verify(gT,gT)\==0 then call err 'game gT not' gT gS=left(game,length(game)-1) /*gS=Game Size (line len for win)*/ if \datatype(gS,'W') then call err "game size isn't numeric:" gS gS=gS/1 if gS<3 then call err "grid size is too small:" gS sw=linesize()-1 indent=left(,max(0,sw-gS-10)%2) /*indentation used board display.*/ empty='fa'x /*the empty grid point symbol. */ @.=empty /*field (grid) is infinite. */ gC= /*GreeK cross character or null. */ CBLF=player\== /*carbon-based lifeform ? */ if CBLF then oFID=player /*oFID is used for the game log. */ oFID=oFID'.LOG' /*fulltype for the LOG's filename*/ prompt='enter X,Y point and an optional character for placing on board',
'(or Quit):'; prompt=right(prompt,79,'─') /*right justify it.*/
call GreekCross jshots=Gshots
do turns=1 for 1000
if CBLF then do
call t prompt; pull stuff; stuff=translate(stuff,,',')
parse var stuff px py p
_=px; upper _; if abbrev('QUIT',_,1) then exit
if stuff== then do; call display; iterate; end
call mark px,py
end /*if CBLF*/
else do; quiet=1
shot=translate(word(Gshots,turn),,',')
if shot== then do 50
xr=loX-1+random(0,hiX-loX+2)
yr=loY-1+random(0,hiY-loY+2)
if @.xr.yr\==empty then iterate
if \neighbor(xr,yr) then iterate
shot=xr yr
end
call mark word(shot,1),word(shot,2)
end
end /*forever*/
call t '* number of wins =' wins exit wins /*stick a fork in it, we're done.*/ /*───────────────────────────────error handling subroutines and others.─*/ err: if \quiet then do; call t; call t
call t center(' error! ',max(40,linesize()%2),"*"); call t
do j=1 for arg(); call t arg(j); call t; end; call t
end
if prompt== then exit 13; return
novalue: syntax: prompt=; quiet=0
call err 'REXX program' condition('C') "error",,
condition('D'),'REXX source statement (line' sigl"):",,
sourceline(sigl)
t: say arg(1); call lineout oFID,arg(1); return Gshot: Gshots=Gshots arg(1)','arg(2); return tranGC: if gC== then return arg(1); return translate(arg(1),copies(gC,12),'┌┐└┘│─╔╗╚╝║═') /*─────────────────────────────────────GREEKCROSS subroutine────────────*/ GreekCross: wins=0; loX=-1; hiX=0; LB=gS-1 /*Low Bar*/
lintel=LB-2; turn=1; loY=-1; hiY=0; ht=4+3*(LB-2) /*─ ─ */
Gshots=; nook=gS-2; Hnook=ht-nook+1; TB=ht-LB+1 /*Top Bar*/
/*─ ─ */
do y=1 for ht; _top='╔'copies('═',lintel)'╗' ; _top=tranGC(_top)
_bot='╚'copies('═',lintel)'╝' ; _bot=tranGC(_bot)
_hib='╔'copies('═',lintel)'╝'left(,lintel)'╚'copies('═',lintel)'╗' ; _hib=tranGC(_hib)
_lob='╚'copies('═',lintel)'╗'left(,lintel)'╔'copies('═',lintel)'╝' ; _lob=tranGC(_lob)
_sid='║' ; _sid=tranGC(_sid)
select
when y==1 then do x=1 for LB; call place x+LB-1,y,substr(_bot,x,1); end
when y==ht then do x=1 for LB; call place x+LB-1,y,substr(_top,x,1); end
when y==LB then do x=1 for ht; if x>LB & x<TB then iterate; call place x,y,substr(_lob,x,1); end
when y==TB then do x=1 for ht; if x>LB & x<TB then iterate; call place x,y,substr(_hib,x,1); end
when y>LB & y<TB then do x=1 by ht-1 for 2; call place x,y,_sid; end
otherwise do x=LB by TB-LB for 2; call place x,y,_sid; end
end /*select*/
end /*y*/
@abc='abcdefghijklmnopqrstuvwxyz'; @chars='0123456789'translate(@abc)||@abc @chars=@chars'()[]{}<>«»' /*can't contain "empty", ?, blank*/
call display call Gshot nook , nook ; call Gshot nook , Hnook call Gshot Hnook , nook ; call Gshot Hnook , Hnook call Gshot gS , LB ; call Gshot gS , TB call Gshot ht-LB , LB ; call Gshot ht-LB , TB call Gshot LB , gS ; call Gshot TB , gS call Gshot LB , TB-1 ; call Gshot TB , TB-1 call Gshot 1 , TB+1 ; call Gshot ht , TB+1 call Gshot TB+1 , 1 ; call Gshot TB+1 , ht return /*─────────────────────────────────────DISPLAY subroutine───────────────*/ display: call t; do y=hiY to loY by -1; _=indent /*start at a high Y.*/
do x=loX to hiX /*build an "X" line.*/
!=@.x.y; xo=x==0; yo=y==0
if !==empty then do /*grid transformation*/
if xo then !='|'
if xo & y//5 ==0 then !='├'
if xo & y//10==0 then !='╞'
if yo then !='─'
if yo & x//5 ==0 then !='┴'
if yo & x//10==0 then !='╨'
if xo & yo then !='┼'
end
_=_ || !
end /*x*/
call t _ /*...and display it.*/
end /*y*/
if wins==0 then call t copies('═',79)
else call t right('count of (above) wins =' wins,79,'═')
call t return /*─────────────────────────────────────PLACE subroutine─────────────────*/ place: parse arg xxp,yyp /*place a marker (point) on grid.*/ loX=min(loX,xxp); hiX=max(hiX,xxp) loY=min(loY,yyp); hiY=max(hiY,yyp); @.xxp.yyp=arg(3) return /*─────────────────────────────────────MARK subroutine──────────────────*/ mark: parse arg xx,yy,pointChar /*place marker, check for errors.*/ if pointChar== then pointChar=word(substr(@chars,turn,1) '+',1) xxcyy=xx','yy; _.1=xx; _.2=yy
do j=1 for 2; XorY=substr('XY',j,1) /*make sure X and Y are integers.*/
if _.j== then do; call err XorY "wasn't specified." ; return 0; end
if \datatype(_.j,'N') then do; call err XorY "isn't numeric:" _.j ; return 0; end
if \datatype(_.j,'W') then do; call err XorY "isn't an integer:" _.j; return 0; end
end
xx=xx/1; yy=yy/1 /*normalize integers: + 7 or 5.0*/
if pointChar==empty |,
pointChar=='?' then do; call err 'illegal point character:' pointChar; return 0; end
if @.xx.yy\==empty then do; call err 'point' xxcyy 'is already occupied.'; return 0; end if \neighbor(xx,yy) then do; call err "point" xxcyy "is a bad move." ; return 0; end call place xx,yy,'?' newWins=countWins() if newWins==0 then do; call err "point" xxcyy "isn't a good move."
@.xx.yy=empty
return 0
end
call t "move" turn ' ('xx","yy') with "'pointChar'"' wins=wins+newWins; @.xx.yy=pointChar; call display; turn=turn+1 return 1 /*─────────────────────────────────────NEIGHBOR subroutine──────────────*/ neighbor: parse arg a,b; am=a-1; ap=a+1
bm=b-1; bp=b+1
return @.am.b \== empty | @.am.bm \== empty |,
@.ap.b \== empty | @.am.bp \== empty |,
@.a.bm \== empty | @.ap.bm \== empty |,
@.a.bp \== empty | @.ap.bp \== empty
/*─────────────────────────────────────COUNTALINE subroutine────────────*/ countAline: arg z ; L=length(z)
if L>gS then do; if gT=='D' then return 0 /*longlines ¬ kosker for D*/
parse var z z1 '?' z2 /*could be xxxxx?xxxx */
return length(z1)==4 | length(z2)==4
end
return L==gS /*─────────────────────────────────────COUNTWINS subroutine─────────────*/ countWins: eureka=0; y=yy /*count horizontal/vertical/diagonal wins.*/ z=@.xx.yy
do x=xx+1; if @.x.y==empty then leave; z=z||@.x.y; end
do x=xx-1 by -1; if @.x.y==empty then leave; z=@.x.y||z; end
eureka=eureka+countAline(z) /*─────────count wins in horizontal line. */
x=xx z=@.xx.yy
do y=yy+1; if @.x.y==empty then leave; z=z||@.x.y; end
do y=yy-1 by -1; if @.x.y==empty then leave; z=@.x.y||z; end
eureka=eureka+countAline(z) /*─────────count wins in vertical line. */
x=xx z=@.xx.yy
do y=yy+1; x=x+1; if @.x.y==empty then leave; z=z||@.x.y; end
x=xx
do y=yy-1 by -1; x=x-1; if @.x.y==empty then leave; z=@.x.y||z; end
eureka=eureka+countAline(z) /*───────count diag wins: up&>, down&< */
x=xx z=@.xx.yy
do y=yy+1; x=x-1; if @.x.y==empty then leave; z=z||@.x.y; end
x=xx
do y=yy-1 by -1; x=x+1; if @.x.y==empty then leave; z=z||@.x.y; end
return eureka+countAline(z) /*───────count diag wins: up&<, down&> */
</lang> output when running 1,500 trials, the highest win was a meager 44 (four games, all different), and one of them is shown below.
·╞···╔══╗···
·|···║··║···
·|···║··║···
·|╔══╝··╚══╗
·|║········║
·├║········║
·|╚══╗··╔══╝
·|···║··║···
·|···║··║···
·|···╚══╝···
─┼────┴────╨
·|··········
═══════════════════════════════════════════════════════════════════════════════
move 1 (3,3) with "0"
... previous 46 moves elided ... above is the initial board (grid) ...
--- the next line means: 47th move, position=9,9 marked with an "k" ---
move 47 (9,9) with "k"
·|············
·|··iQagP·····
·╞j·d╔══╗F····
·|·hO║NL║ck···
·|CZ1║bK║3MD··
·X╔══╝57╚══╗f·
·|║YHASGBJR║··
·├║UT8I·9·e║··
·|╚══╗46╔══╝··
·V··0║W·║2····
·|···║··║·····
·|···╚══╝E····
─┼────┴────╨──
·|············
═════════════════════════════════════════════════════ count of (above) wins = 47
* number of wins = 47