IM204 Coursework 2: Noughts and Crosses

!---------------------------------------------------------------------------
! IM204 Coursework 2: Noughts and Crosses -  Eamonn Martin - ID: 96/D59682
!---------------------------------------------------------------------------

! Cell states
data symbols == space ++ nought ++ cross;

! Grid structure
type state == symbols;
type row   == list (state);
type grid  == list (row);

! Return the unoccupied-cell state
dec unoccupied : state;
--- unoccupied <= space;

!---------------------------------------------------------------------------
! Part 1 - List all grids possible after adding a symbol to a grid
!---------------------------------------------------------------------------

! Return the number of items in a list
dec count : list (alpha) -> num ;
--- count ( [] ) <= 0;
--- count ( n :: m ) <= 1 + count(m);

! Return row wih state s at position i (if i is within row)
dec getrow : row # num # state -> row;
--- getrow ( [], i, s ) <= [];
--- getrow ( n :: m, i, s ) <=
    (if (i=0) then [s] else [n]) <> getrow(m, i-1, s);

! Return grid with position i set to state s
dec getgrid : grid # num # state -> grid;
--- getgrid ( [], i, s ) <= [];
--- getgrid ( n :: m, i, s ) <=
    [getrow( n, i, s )] <> getgrid(m, i-count(n), s);

! Return a grid for each space-cell in row set to state s
dec cellgrids : grid # num # state # row -> list (grid);
--- cellgrids ( g, i, s, [] ) <= [];
--- cellgrids ( g, i, s, n :: m ) <=
    if (n /= unoccupied) then therest
    else [getgrid(g, i, s)] <> therest
    where therest == cellgrids(g, i+1, s, m);

! Return a grid for each space-cell in grid set to state s
dec getgrids : grid # num # state # grid -> list (grid);
--- getgrids ( g, i, s, [] ) <= [];
--- getgrids ( g, i, s, n :: m ) <=
    cellgrids( g, i, s, n ) <> getgrids(g, i+count(n), s, m);

! Return all grids possible after adding state s to grid
dec nextgrids : grid # state -> list (grid);
--- nextgrids ( g, s ) <= getgrids(g, 0, s, g);


!---------------------------------------------------------------------------
! Part 2 - Score each possible grid and list those with the highest score
!---------------------------------------------------------------------------

dec rowstate : row # num -> state;
--- rowstate ( [], i ) <= unoccupied;
--- rowstate ( n :: m, i ) <=
    if (i=0) then n else rowstate(m, i-1);

dec cellstate : grid # num # num -> state;
--- cellstate ( [], x, y ) <= unoccupied;
--- cellstate ( n :: m, x, y ) <=
    if (y=0) then rowstate(n, x) else cellstate(m, x, y-1);

! Return the value to player s of cell x,y in grid g
dec cell : grid # num # num # state -> num;
--- cell ( g, x, y, s ) <=
    if (v = unoccupied) then 0
    else if (v = s) then 2 else 1
    where v == cellstate(g, x, y);

dec cellvalue : grid # num # num # num # state -> num;
--- cellvalue ( g, x, y, z, s ) <=
    cell(g,x-z,y-z,s) + cell(g,x,y-z,s) + cell(g,x+z,y-z,s) +
    cell(g,x-z,y  ,s)           +         cell(g,x+z,y  ,s) +
    cell(g,x-z,y+z,s) + cell(g,x,y+z,s) + cell(g,x+z,y+z,s) ;

dec cellscore : grid # num # num # state # state -> num;
--- cellscore ( g, x, y, s, c ) <=
    if (c = unoccupied) then 0
    else if (c = s) then v else (0-v)
    where v == cellvalue(g, x, y, 1, s) +
               cellvalue(g, x, y, 2, s) ;

dec rowscore : grid # num # num # state # row -> num;
--- rowscore ( g, x, y, s, [] ) <= 0;
--- rowscore ( g, x, y, s, n :: m ) <=
    cellscore(g, x, y, s, n) + rowscore(g, x+1, y, s, m);

dec gridscore : grid # num # state # grid -> num;
--- gridscore ( g, y, s, [] ) <= 0;
--- gridscore ( g, y, s, n :: m ) <=
    rowscore(g, 0, y, s, n) + gridscore(g, y+1, s, m);

dec bestmoves : list (grid) # state # num # list (grid) -> list (grid);
--- bestmoves ( [], s, max, g ) <= g;
--- bestmoves ( n :: m, s, max, g ) <=
    if (score < max) then bestmoves(m, s, max, g)
    else if (score > max) then bestmoves(m, s, score, [n])
    else bestmoves(m, s, max, g <> [n])
    where score == gridscore(n, 0, s, n);

dec nextmoves : grid # state -> list (grid);
--- nextmoves ( g, s) <=
    bestmoves(nextgrids(g, s), s, 0-99, []);


!---------------------------------------------------------------------------

! Test grids
dec g0, g1, g2, g3 : grid;

! Starting grid
--- g0 <= [[cross,nought,cross],[cross,space,space],[space,nought,nought]];

! Possible next moves
--- g1 <= [[cross,nought,cross],[cross,cross,space],[space,nought,nought]];
--- g2 <= [[cross,nought,cross],[cross,space,cross],[space,nought,nought]];
--- g3 <= [[cross,nought,cross],[cross,space,space],[cross,nought,nought]];

! Grid scores for each move
dec test1, test2, test3 : num;
--- test1 <= gridscore(g1, 0, cross, g1);
--- test2 <= gridscore(g2, 0, cross, g2);
--- test3 <= gridscore(g3, 0, cross, g3);

! Shorthand
dec o, x, . : state;
--- o <= nought;
--- x <= cross;
--- . <= space;

! END