Previous Contents Next

Two Player Games

The application presented in this section pursues two objectives. On the one hand, it seeks to resolve problems related to the complexity in searching state spaces, as well as showing that Objective CAML provides useful tools for dealing with symbolic applications. On the other hand, it also explores the benefits of using parametric modules to define a generic scheme for constructing two player games, providing the ability to factor out one part of the search, and making it easy to customize components such as functions for evaluating or displaying a game position.

We first present the problem of games involving two players, then describe the minimax-ab algorithm which provides an efficient search of the tree of possible moves. We present a parametric model for two player games. Then, we apply these functors to implement two games: ``Connect Four'' (a vertical tic-tac-toe), and Stonehenge (a game that involves constructing ley-lines).

The Problem of Two Player Games

Games involving two players represent one of the classic applications of symbolic programming and provide a good example of problem solving for at least two reasons:

First, assume that we are able to explore the total list of all possible moves, given, as a starting point, a specific legal game position. Such a program will require a function to generate legal moves based on a starting position, as well as a function to evaluate some ``score'' for each resulting position. The evaluation function must give a maximum score to a winning position, and a minimal score to a losing position. After picking an initial position, one may then construct a tree of all possible variations, where each node corresponds to a position, the adjacent siblings are obtained by having played a move and with leaves having positions indicating winning, losing, or null results. Once the tree is constructed, its exploration permits determining if there exists a route leading to victory, or a null position, failing that. The shortest path may then be chosen to attain the desired goal.

As the overall size of such a tree is generally too large for it to be fully represented, it is typically necessary to limit what portions of the tree are constructed. A first strategy is to limit the ``depth'' of the search, that is, the number of moves and responses that are to be evaluated. One thus reduces the breadth of the tree as well as its height. In such cases, leaf nodes will seldom be found until nearly the end of the game.

On the other hand, we may try to limit the number of moves selected for additional evaluation. For this, we try to avoid evaluating any but the most favorable moves, and start by examining the moves that appear to be the very best. This immediately eliminates entire branches of the tree. This leads to the minimax a b algorithm presented in the next subsection.

Minimax ab

We present the minimax search and describe a variant optimized using a b cuts. The implementation of this algorithm uses a parametric module, FAlphabeta along with a representation of the game and its evaluation function. We distinguish between the two players by naming them A and B.

Minimax

The minimax algorithm is a depth-first search algorithm with a limit on the depth to which search is done. It requires:

Starting with some initial game position, the algorithm explores the tree of all legal moves down to the requested depth. Scores associated with leaves of the tree are calculated using an evaluation function. A positive score indicates a good position for player A, while a negative score indicates a poor position for player A, and thus a good position for player B. For each player, the transition from one position to another is either maximized (for player A) or minimized (for player B). Each player tries to select his moves in a manner that will be most profitable for him. In searching for the best play for player A, a search of depth 1 tries to determine the immediate move that maximizes the score of the new position.



Figure 17.1: Maximizing search at a given location.


In figure 17.1, player A starts at position O, finds four legal moves, constructs these new configurations, and evaluates them. Based on these scores, the best position is P2, with a score of 8. This value is propagated to position O, indicating that this position provides a move to a new position, giving a score of 8 when the player moves to C2. The search of depth 1 is, as a general rule, insufficient, as it does not consider the possible response of an adversary. Such a shallow search results in programs that search greedily for immediate material gains (such as the prize of a queen, in chess) without perceiving that the pieces are protected or that the position is otherwise a losing one (such as a gambit of trading one's queen for a mate). A deeper exploration to depth 2 permits perceiving at least the simplest such countermoves.

Figure 17.2 displays a supplementary analysis of the tree that takes into consideration the possible responses of player B. This search considers B's best moves. For this, the minimax algorithm minimizes scores of depth 2.



Figure 17.2: Maximizing and minimizing in depth-2 search.


Move P2, which provided an immediate position score of 8, leads to a position with a score of -3. In effect, if B plays D5, then the score of Q5 will be -3. Based on this deeper examination, the move C1 limits the losses with a score of -1, and is thus the preferred move.

In most games, it is possible to try to confuse the adversary, making him play forced moves, trying to muddle the situation in the hope that he will make a mistake. A shallow search of depth 2 would be completely inadequate for this sort of tactic. These sorts of strategies are rarely able to be well exploited by a program because it has no particular vision as to the likely evolution of the positions towards the end of the game.

The difficulty of increased depth of search comes in the form of a combinatorial ``explosion.'' For example, with chess, the exploration of two additional levels adds a factor of around a thousand times more combinations (30 × 30). Thus, if one searches to a depth of 10, one obtains around 514 positions, which represents too much to search. For this reason, you must try to somehow trim the search tree.

One may note in figure 17.2 that it may be useless to search the branch P3 insofar as the score of this position at depth 1 is poorer than that found in branch P1. In addition the branch P4 does not need to be completely explored. Based on the calculation of Q7, one obtains a score inferior to that of P1, which has already been completely explored. The calculations for Q8 and Q9 cannot improve this situation even if their scores are better than Q7. In a minimizing mode, the poorest score is dropped. The player knows then that these branches provide no useful new options. The minimax variant a b uses this approach to decrease the number of branches that must be explored.

Minimax-ab

We call the a cut the lower limit of a maximizing node, and cut b the upper limit of a minimizing node. Figure 17.3 shows the cuts carried out in branches P3 and P4 based on knowing the lower limit -1 of P1.



Figure 17.3: Limit a to one level max-min.


As soon as the tree gets broader or deeper the number of cuts increases, thus indicating large subtrees.

A Parametric Module for a b Minimax

We want to produce a parametric module, FAlphabeta, implementing this algorithm, which will be generically reusable for all sorts of two player games. The parameters correspond, on the one hand, to all the information about the proceedings of moves in the game, and on the other hand, to the evaluation function.

Interfaces.
We declare two signatures: REPRESENTATION to represent plays; and EVAL to evaluate a position.

# module type REPRESENTATION = 
sig
type game
type move
val game_start : unit -> game
val legal_moves: bool -> game -> move list
val play: bool -> move -> game -> game
end ;;
module type REPRESENTATION =
sig
type game
and move
val game_start : unit -> game
val legal_moves : bool -> game -> move list
val play : bool -> move -> game -> game
end

# module type EVAL =
sig
type game
val evaluate: bool -> game -> int
val moreI : int
val lessI: int
val is_leaf: bool -> game -> bool
val is_stable: bool -> game -> bool
type state = G | P | N | C
val state_of : bool -> game -> state
end ;;
module type EVAL =
sig
type game
val evaluate : bool -> game -> int
val moreI : int
val lessI : int
val is_leaf : bool -> game -> bool
val is_stable : bool -> game -> bool
type state = | G | P | N | C
val state_of : bool -> game -> state
end


Types game and move represent abstract types. A player is represented by a boolean value. The function legal_moves takes a player and position, and returns the list of possible moves. The function play takes a player, a move, and a position, and returns a new position. The values moreI and lessI are the limits of the values returned by function evaluate. The predicate is_leaf verifies if a player in a given position can play. The predicate is_stable indicates whether the position for the player represents a stable position. The results of these functions influence the pursuit of the exploration of moves when one attains the specified depth.

The signature ALPHABETA corresponds to the signature resulting from the complete application of the parametric module that one wishes to use. These hide the different auxiliary functions that we use to implement the algorithm.

# module type ALPHABETA = sig 
type game
type move
val alphabeta : int -> bool -> game -> move
end ;;
module type ALPHABETA =
sig type game and move val alphabeta : int -> bool -> game -> move end


The function alphabeta takes as parameters the depth of the search, the player, and the game position, returning the next move.

We then define the functional signature FALPHABETA which must correspond to that of the implementation of the functor.

# module type FALPHABETA = functor (Rep : REPRESENTATION) 
-> functor (Eval : EVAL with type game = Rep.game)
-> ALPHABETA with type game = Rep.game
and type move = Rep.move ;;
module type FALPHABETA =
functor(Rep : REPRESENTATION) ->
functor
(Eval : sig
type game = Rep.game
val evaluate : bool -> game -> int
val moreI : int
val lessI : int
val is_leaf : bool -> game -> bool
val is_stable : bool -> game -> bool
type state = | G | P | N | C
val state_of : bool -> game -> state
end) ->
sig
type game = Rep.game
and move = Rep.move
val alphabeta : int -> bool -> game -> move
end


Implementation.
The parametric module FAlphabetaO makes explicit the partition of the type game between the two parameters Rep and Eval. This module has six functions and two exceptions. The player true searches to maximize the score while the player false seeks to minimize the score. The function maxmin_iter calculates the maximum of the best score for the branches based on a move of player true and the pruning parameter a.

The function maxmin takes four parameters: depth, which indicates the actual calculation depth, node, a game position, and a and b, the pruning parameters. If the node is a leaf of the tree or if the maximum depth is reached, the function will return its evaluation of the position. If this is not the case, the function applies maxmin_iter to all of the legal moves of player true, passing it the search function, diminishing the depth remaining (minmax). The latter searches to minimize the score resulting from the response of player false.

The movements are implemented using exceptions. If the move b is found in the iteration across the legal moves from the function maxmin, then it is returned immediately, the value being propagated using an exception. The functions minmax_iter and minmax provide the equivalents for the other player. The function search determines the move to play based on the best score found in the lists of scores and moves.

The principal function alphabeta of this module calculates the legal moves from a given position for the requested player, searches down to the requested depth, and returns the best move.

# module FAlphabetaO 
(Rep : REPRESENTATION) (Eval : EVAL with type game = Rep.game) =
struct
type game = Rep.game
type move = Rep.move
exception AlphaMovement of int
exception BetaMovement of int

let maxmin_iter node minmax_cur beta alpha cp =
let alpha_resu =
max alpha (minmax_cur (Rep.play true cp node) beta alpha)
in if alpha_resu >= beta then raise (BetaMovement alpha_resu)
else alpha_resu

let minmax_iter node maxmin_cur alpha beta cp =
let beta_resu =
min beta (maxmin_cur (Rep.play false cp node) alpha beta)
in if beta_resu <= alpha then raise (AlphaMovement beta_resu)
else beta_resu

let rec maxmin depth node alpha beta =
if (depth < 1 & Eval.is_stable true node)
or Eval.is_leaf true node
then Eval.evaluate true node
else
try let prev = maxmin_iter node (minmax (depth - 1)) beta
in List.fold_left prev alpha (Rep.legal_moves true node)
with BetaMovement a -> a

and minmax depth node beta alpha =
if (depth < 1 & Eval.is_stable false node)
or Eval.is_leaf false node
then Eval.evaluate false node
else
try let prev = minmax_iter node (maxmin (depth - 1)) alpha
in List.fold_left prev beta (Rep.legal_moves false node)
with AlphaMovement b -> b

let rec search a l1 l2 = match (l1,l2) with
(h1::q1, h2::q2) -> if a = h1 then h2 else search a q1 q2
| ([], []) -> failwith ("AB: "^(string_of_int a)^" not found")
| (_ , _) -> failwith "AB: length differs"

(* val alphabeta : int -> bool -> Rep.game -> Rep.move *)
let alphabeta depth player level =
let alpha = ref Eval.lessI and beta = ref Eval.moreI in
let l = ref [] in
let cpl = Rep.legal_moves player level in
let eval =
try
for i = 0 to (List.length cpl) - 1 do
if player then
let b = Rep.play player (List.nth cpl i) level in
let a = minmax (depth-1) b !beta !alpha
in l := a :: !l ;
alpha := max !alpha a ;
(if !alpha >= !beta then raise (BetaMovement !alpha))
else
let a = Rep.play player (List.nth cpl i) level in
let b = maxmin (depth-1) a !alpha !beta
in l := b :: !l ;
beta := min !beta b ;
(if !beta <= !alpha then raise (AlphaMovement !beta))
done ;
if player then !alpha else !beta
with
BetaMovement a -> a
| AlphaMovement b -> b
in
l := List.rev !l ;
search eval !l cpl
end ;;
module FAlphabetaO :
functor(Rep : REPRESENTATION) ->
functor
(Eval : sig
type game = Rep.game
val evaluate : bool -> game -> int
val moreI : int
val lessI : int
val is_leaf : bool -> game -> bool
val is_stable : bool -> game -> bool
type state = | G | P | N | C
val state_of : bool -> game -> state
end) ->
sig
type game = Rep.game
and move = Rep.move
exception AlphaMovement of int
exception BetaMovement of int
val maxmin_iter :
Rep.game ->
(Rep.game -> int -> int -> int) -> int -> int -> Rep.move -> int
val minmax_iter :
Rep.game ->
(Rep.game -> int -> int -> int) -> int -> int -> Rep.move -> int
val maxmin : int -> Eval.game -> int -> int -> int
val minmax : int -> Eval.game -> int -> int -> int
val search : int -> int list -> 'a list -> 'a
val alphabeta : int -> bool -> Rep.game -> Rep.move
end


We may close module FAlphabetaO by associating with it the following signature:


# module FAlphabeta = (FAlphabetaO : FALPHABETA) ;;
module FAlphabeta : FALPHABETA


This latter module may be used with many different game representations and functions to play different games.

Organization of a Game Program

The organization of a program for a two player game may be separated into a portion specific to the game in question as well as a portion applicable to all sorts of games. For this, we propose using several parametric modules parameterized by specific modules, permitting us to avoid the need to rewrite the common portions each time. Figure 17.4 shows the chosen organization.



Figure 17.4: Organization of a game application.


The modules with no highlighting correspond to the common parts of the application. These are the parametric modules. We see again the functor FAlphabeta. The modules with gray highlighting are the modules designed specifically for a given game. The three principal modules are the representation of the game (J_Repr), display of the game (J_Disp), and the evaluation function (J_Eval). The modules with rounded gray borders are obtained by applying the parametric modules to the simple modules specific to the game.

The module FAlphabeta has already been described. The two other common modules are FMain, containing the main loop, and FSkeleton, that manages the players.

Module FMain

Module FMain contains the main loop for execution of a game program. It is parameterized using the signature module SKELETON, describing the interaction with a player using the following definition:

# module type SKELETON = sig 
val home: unit -> unit
val init: unit -> ((unit -> unit) * (unit -> unit))
val again: unit -> bool
val exit: unit -> unit
val won: unit -> unit
val lost: unit -> unit
val nil: unit -> unit
exception Won
exception Lost
exception Nil
end ;;
module type SKELETON =
sig
val home : unit -> unit
val init : unit -> (unit -> unit) * (unit -> unit)
val again : unit -> bool
val exit : unit -> unit
val won : unit -> unit
val lost : unit -> unit
val nil : unit -> unit
exception Won
exception Lost
exception Nil
end



The function init constructs a pair of action functions for each player. The other functions control the interactions. Module FMain contains two functions: play_game which alternates between the players, and main which controls the main loop.

# module FMain (P : SKELETON) = 
struct
let play_game movements = while true do (fst movements) () ;
(snd movements) () done

let main () = let finished = ref false
in P.home ();
while not !finished do
( try play_game (P.init ())
with P.Won -> P.won ()
| P.Lost -> P.lost ()
| P.Nil -> P.nil () );
finished := not (P.again ())
done ;
P.exit ()
end ;;
module FMain :
functor(P : SKELETON) ->
sig
val play_game : (unit -> 'a) * (unit -> 'b) -> unit
val main : unit -> unit
end


Module FSkeleton

Parametric module FSkeleton controls the moves of each player according to the rules provided at the start of the section based on the nature of the players (automated or not) and the order of the players. It needs various parameters to represent the game, game states, the evaluation function, and the a b search as described in figure 17.4.

We start with the signature needed for game display.

# module type DISPLAY = sig 
type game
type move
val home: unit -> unit
val exit: unit -> unit
val won: unit -> unit
val lost: unit -> unit
val nil: unit -> unit
val init: unit -> unit
val position : bool -> move -> game -> game -> unit
val choice : bool -> game -> move
val q_player : unit -> bool
val q_begin : unit -> bool
val q_continue : unit -> bool
end ;;
module type DISPLAY =
sig
type game
and move
val home : unit -> unit
val exit : unit -> unit
val won : unit -> unit
val lost : unit -> unit
val nil : unit -> unit
val init : unit -> unit
val position : bool -> move -> game -> game -> unit
val choice : bool -> game -> move
val q_player : unit -> bool
val q_begin : unit -> bool
val q_continue : unit -> bool
end


It is worth noting that the representation of the game and of the moves must be shared by all the parametric modules, which constrain the types. The two principal functions are playH and playM, respectively controlling the move of a human player (using the function Disp.choice) and that of an automated player. The function init determines the nature of the players and the sorts of responses for Disp.q_player.

# module FSkeleton 
(Rep : REPRESENTATION)
(Disp : DISPLAY with type game = Rep.game and type move = Rep.move)
(Eval : EVAL with type game = Rep.game)
(Alpha : ALPHABETA with type game = Rep.game and type move = Rep.move) =
struct
let depth = ref 4
exception Won
exception Lost
exception Nil
let won = Disp.won
let lost = Disp.lost
let nil = Disp.nil
let again = Disp.q_continue
let play_game = ref (Rep.game_start())
let exit = Disp.exit
let home = Disp.home

let playH player () =
let choice = Disp.choice player !play_game in
let old_game = !play_game
in play_game := Rep.play player choice !play_game ;
Disp.position player choice old_game !play_game ;
match Eval.state_of player !play_game with
Eval.P -> raise Lost
| Eval.G -> raise Won
| Eval.N -> raise Nil
| _ -> ()

let playM player () =
let choice = Alpha.alphabeta !depth player !play_game in
let old_game = !play_game
in play_game := Rep.play player choice !play_game ;
Disp.position player choice old_game !play_game ;
match Eval.state_of player !play_game with
Eval.G -> raise Won
| Eval.P -> raise Lost
| Eval.N -> raise Nil
| _ -> ()

let init () =
let a = Disp.q_player () in
let b = Disp.q_player()
in play_game := Rep.game_start () ;
Disp.init () ;
match (a,b) with
true,true -> playM true, playM false
| true,false -> playM true, playH false
| false,true -> playH true, playM false
| false,false -> playH true, playH false
end ;;
module FSkeleton :
functor(Rep : REPRESENTATION) ->
functor
(Disp : sig
type game = Rep.game
and move = Rep.move
val home : unit -> unit
val exit : unit -> unit
val won : unit -> unit
val lost : unit -> unit
val nil : unit -> unit
val init : unit -> unit
val position : bool -> move -> game -> game -> unit
val choice : bool -> game -> move
val q_player : unit -> bool
val q_begin : unit -> bool
val q_continue : unit -> bool
end) ->
functor
(Eval : sig
type game = Rep.game
val evaluate : bool -> game -> int
val moreI : int
val lessI : int
val is_leaf : bool -> game -> bool
val is_stable : bool -> game -> bool
type state = | G | P | N | C
val state_of : bool -> game -> state
end) ->
functor
(Alpha : sig
type game = Rep.game
and move = Rep.move
val alphabeta : int -> bool -> game -> move
end) ->
sig
val depth : int ref
exception Won
exception Lost
exception Nil
val won : unit -> unit
val lost : unit -> unit
val nil : unit -> unit
val again : unit -> bool
val play_game : Disp.game ref
val exit : unit -> unit
val home : unit -> unit
val playH : bool -> unit -> unit
val playM : bool -> unit -> unit
val init : unit -> (unit -> unit) * (unit -> unit)
end


The independent parts of the game are thus implemented. One may then begin programming different sorts of games. This modular organization facilitates making modifications to the movement scheme or to the evaluation function for a game as we shall soon see.

Connect Four

We will next examine a simple game, a vertical tic-tac-toe, known as Connect Four. The game is represented by seven columns each consisting of six lines. In turn, a player places on a column a piece of his color, where it then falls down to the lowest free location in this column. If a column is completely filled, neither player is permitted to play there. The game ends when one of the players has built a line of four pieces in a row (horizontal, vertical, or diagonal), at which point this player has won, or when all the columns are filled with pieces, in which the outcome is a draw. Figure 17.5 shows a completed game.



Figure 17.5: An example of Connect Four.


Note the ``winning'' line of four gray pieces in a diagonal, going down and to the right.

Game Representation: module C4_rep.
We choose for this game a matrix-based representation. Each element of the matrix is either empty, or contains a player's piece. A move is numbered by the column. The legal moves are the columns in which the final (top) row is not filled.

# module C4_rep = struct
type cell = A | B | Empty
type game = cell array array
type move = int
let col = 7 and row = 6
let game_start () = Array.create_matrix row col Empty

let legal_moves b m =
let l = ref [] in
for c = 0 to col-1 do if m.(row-1).(c) = Empty then l := (c+1) :: !l done;
!l

let augment mat c =
let l = ref row
in while !l > 0 & mat.(!l-1).(c-1) = Empty do decr l done ; !l + 1

let player_gen cp m e =
let mj = Array.map Array.copy m
in mj.((augment mj cp)-1).(cp-1) <- e ; mj

let play b cp m = if b then player_gen cp m A else player_gen cp m B
end ;;
module C4_rep :
sig
type cell = | A | B | Empty
and game = cell array array
and move = int
val col : int
val row : int
val game_start : unit -> cell array array
val legal_moves : 'a -> cell array array -> int list
val augment : cell array array -> int -> int
val player_gen : int -> cell array array -> cell -> cell array array
val play : bool -> int -> cell array array -> cell array array
end


We may easily verify if this module accepts the constraints of the signature REPRESENTATION.


# module C4_rep_T = (C4_rep : REPRESENTATION) ;;
module C4_rep_T : REPRESENTATION


Game Display: Module C4_text.
Module C4_text describes a text-based interface for the game Connect Four that is compatible with the signature DISPLAY. It it is not particularly sophisticated, but, nonetheless, demonstrates how modules are assembled together.

# module C4_text = struct
open C4_rep
type game = C4_rep.game
type move = C4_rep.move

let print_game mat =
for l = row - 1 downto 0 do
for c = 0 to col - 1 do
match mat.(l).(c) with
A -> print_string "X "
| B -> print_string "O "
| Empty -> print_string ". "
done;
print_newline ()
done ;
print_newline ()

let home () = print_string "C4 ...\n"
let exit () = print_string "Bye for now ... \n"
let question s =
print_string s;
print_string " y/n ? " ;
read_line() = "y"
let q_begin () = question "Would you like to begin?"
let q_continue () = question "Play again?"
let q_player () = question "Is there to be a machine player ?"

let won ()= print_string "The first player won" ; print_newline ()
let lost () = print_string "The first player lost" ; print_newline ()
let nil () = print_string "Stalemate" ; print_newline ()

let init () =
print_string "X: 1st player O: 2nd player";
print_newline () ; print_newline () ;
print_game (game_start ()) ; print_newline()

let position b c aj j = print_game j

let is_move = function '1'..'7' -> true | _ -> false

exception Move of int
let rec choice player game =
print_string ("Choose player" ^ (if player then "1" else "2") ^ " : ") ;
let l = legal_moves player game
in try while true do
let i = read_line()
in ( if (String.length i > 0) && (is_move i.[0])
then let c = (int_of_char i.[0]) - (int_of_char '0')
in if List.mem c l then raise (Move c) );
print_string "Invalid move - try again"
done ;
List.hd l
with Move i -> i
| _ -> List.hd l
end ;;
module C4_text :
sig
type game = C4_rep.game
and move = C4_rep.move
val print_game : C4_rep.cell array array -> unit
val home : unit -> unit
val exit : unit -> unit
val question : string -> bool
val q_begin : unit -> bool
val q_continue : unit -> bool
val q_player : unit -> bool
val won : unit -> unit
val lost : unit -> unit
val nil : unit -> unit
val init : unit -> unit
val position : 'a -> 'b -> 'c -> C4_rep.cell array array -> unit
val is_move : char -> bool
exception Move of int
val choice : bool -> C4_rep.cell array array -> int
end


We may immediately verify that this conforms to the constraints of the signature DISPLAY


# module C4_text_T = (C4_text : DISPLAY) ;;
module C4_text_T : DISPLAY


Evaluation Function: module C4_eval.
The quality of a game player depends primarily on the position evaluation function. Module C4_eval defines evaluate, which evaluates the value of a position for the specified player. This function calls eval_bloc for the four compass directions as well as the diagonals. eval_bloc then calls eval_four to calculate the number of pieces in the requested line. Table value provides the value of a block containing 0, 1, 2, or 3 pieces of the same color. The exception Four is raised when 4 pieces are aligned.

# module C4_eval = struct open C4_rep type game = C4_rep.game 
let value =
Array.of_list [0; 2; 10; 50]
exception Four of int
exception Nil_Value
exception Arg_invalid
let lessI = -10000
let moreI = 10000
let eval_four m l_dep c_dep delta_l delta_c =
let n = ref 0 and e = ref Empty
and x = ref c_dep and y = ref l_dep
in try
for i = 1 to 4 do
if !y<0 or !y>=row or !x<0 or !x>=col then raise Arg_invalid ;
( match m.(!y).(!x) with
A -> if !e = B then raise Nil_Value ;
incr n ;
if !n = 4 then raise (Four moreI) ;
e := A
| B -> if !e = A then raise Nil_Value ;
incr n ;
if !n = 4 then raise (Four lessI);
e := B;
| Empty -> () ) ;
x := !x + delta_c ;
y := !y + delta_l
done ;
value.(!n) * (if !e=A then 1 else -1)
with
Nil_Value | Arg_invalid -> 0

let eval_bloc m e cmin cmax lmin lmax dx dy =
for c=cmin to cmax do for l=lmin to lmax do
e := !e + eval_four m l c dx dy
done done

let evaluate b m =
try let evaluation = ref 0
in (* evaluation of rows *)
eval_bloc m evaluation 0 (row-1) 0 (col-4) 0 1 ;
(* evaluation of columns *)
eval_bloc m evaluation 0 (col-1) 0 (row-4) 1 0 ;
(* diagonals coming from the first line (to the right) *)
eval_bloc m evaluation 0 (col-4) 0 (row-4) 1 1 ;
(* diagonals coming from the first line (to the left) *)
eval_bloc m evaluation 1 (row-4) 0 (col-4) 1 1 ;
(* diagonals coming from the last line (to the right) *)
eval_bloc m evaluation 3 (col-1) 0 (row-4) 1 (-1) ;
(* diagonals coming from the last line (to the left) *)
eval_bloc m evaluation 1 (row-4) 3 (col-1) 1 (-1) ;
!evaluation
with Four v -> v

let is_leaf b m = let v = evaluate b m
in v=moreI or v=lessI or legal_moves b m = []

let is_stable b j = true

type state = G | P | N | C

let state_of player m =
let v = evaluate player m
in if v = moreI then if player then G else P
else if v = lessI then if player then P else G
else if legal_moves player m = [] then N else C
end ;;
module C4_eval :
sig
type game = C4_rep.game
val value : int array
exception Four of int
exception Nil_Value
exception Arg_invalid
val lessI : int
val moreI : int
val eval_four :
C4_rep.cell array array -> int -> int -> int -> int -> int
val eval_bloc :
C4_rep.cell array array ->
int ref -> int -> int -> int -> int -> int -> int -> unit
val evaluate : 'a -> C4_rep.cell array array -> int
val is_leaf : 'a -> C4_rep.cell array array -> bool
val is_stable : 'a -> 'b -> bool
type state = | G | P | N | C
val state_of : bool -> C4_rep.cell array array -> state
end


Module C4_eval is compatible with the constraints of signature EVAL.


# module C4_eval_T = (C4_eval : EVAL) ;;
module C4_eval_T : EVAL


To play two evaluation functions against one another, it is necessary to modify evaluate to apply the proper evaluation function for each player.

Assembly of the modules
All the components needed to realize the game of Connect Four are now implemented. We only need assemble them together based on the schema of diagram 17.4. First, we construct C4_skeleton, which is the application of parameter module FSkeleton to modules C4_rep, C4_text, C4_eval and the result of the application of parametric module FAlphaBeta to C4_rep and C4_eval.


# module C4_skeleton =
FSkeleton (C4_rep) (C4_text) (C4_eval) (FAlphabeta (C4_rep) (C4_eval)) ;;
module C4_skeleton :
sig
val depth : int ref
exception Won
exception Lost
exception Nil
val won : unit -> unit
val lost : unit -> unit
val nil : unit -> unit
val again : unit -> bool
val play_game : C4_text.game ref
val exit : unit -> unit
val home : unit -> unit
val playH : bool -> unit -> unit
val playM : bool -> unit -> unit
val init : unit -> (unit -> unit) * (unit -> unit)
end


We then obtain the principal module C4_main by applying parametric module FMain on the result of the preceding application C4_skeleton


# module C4_main = FMain(C4_skeleton) ;;
module C4_main :
sig
val play_game : (unit -> 'a) * (unit -> 'b) -> unit
val main : unit -> unit
end


The game is initiated by the application of function C4_main.main on ().

Testing the Game.
Once the general game skeleton has been written, games may be played in various ways. Two human players may play against each other, with the program merely verifying the validity of the moves; a person may play against a programmed player; or programs may play against each other. While this last mode might not be interesting for the human, it does make it easy to run tests without having to wait for a person's responses. The following game demonstrates this scenario.

# C4_main.main () ;;
C4 ...
Is there to be a machine player ? y/n ? y
Is there to be a machine player ? y/n ? y
X: 1st player   O: 2nd player

. . . . . . . 
. . . . . . . 
. . . . . . . 
. . . . . . . 
. . . . . . . 
. . . . . . . 
Once the initial position is played, player 1 (controlled by the program) calculates its move which is then applied.

. . . . . . . 
. . . . . . . 
. . . . . . . 
. . . . . . . 
. . . . . . . 
. . . . . X . 
Player 2 (always controlled by the program) calculates its response and the game proceeds, until a game-ending move is found. In this example, player 1 wins the game based on the following final position:

. O O O . O . 
. X X X . X . 
X O O X . O . 
X X X O . X . 
X O O X X O . 
X O O O X X O 
Player 1 wins
Play again(y/n) ? n
Good-bye ... 
- : unit = ()
Graphical Interface.
To improve the enjoyment of the game, we define a graphical interface for the program, by defining a new module, C4_graph, compatible with the signature DISPLAY, which opens a graphical window, controlled by mouse clicks. The text of this module may be found in the subdirectory Applications on the CD-ROM (see page ??).

# module C4_graph = struct
open C4_rep
type game = C4_rep.game
type move = C4_rep.move
let r = 20 (* color of piece *)
let ec = 10 (* distance between pieces *)
let dec = 30 (* center of first piece *)
let cote = 2*r + ec (* height of a piece looked at like a checker *)
let htexte = 25 (* where to place text *)
let width = col * cote + ec (* width of the window *)
let height = row * cote + ec + htexte (* height of the window *)
let height_of_game = row * cote + ec (* height of game space *)
let hec = height_of_game + 7 (* line for messages *)
let lec = 3 (* columns for messages *)
let margin = 4 (* margin for buttons *)
let xb1 = width / 2 (* position x of button1 *)
let xb2 = xb1 + 30 (* position x of button2 *)
let yb = hec - margin (* position y of the buttons *)
let wb = 25 (* width of the buttons *)
let hb = 16 (* height of the buttons *)

(* val t2e : int -> int *)
(* Convert a matrix coordinate into a graphical coordinate *)
let t2e i = dec + (i-1)*cote

(* The Colors *)
let cN = Graphics.black (* trace *)
let cA = Graphics.red (* Human player *)
let cB = Graphics.yellow (* Machine player *)
let cF = Graphics.blue (* Game Background color *)
(* val draw_table : unit -> unit : Trace an empty table *)
let draw_table () =
Graphics.clear_graph();
Graphics.set_color cF;
Graphics.fill_rect 0 0 width height_of_game;
Graphics.set_color cN;
Graphics.moveto 0 height_of_game;
Graphics.lineto width height_of_game;
for l = 1 to row do
for c = 1 to col do
Graphics.draw_circle (t2e c) (t2e l) r
done
done

(* val draw_piece : int -> int -> Graphics.color -> unit *)
(* 'draw_piece l c co' draws a piece of color co at coordinates l c *)
let draw_piece l c col =
Graphics.set_color col;
Graphics.fill_circle (t2e c) (t2e l) (r+1)

(* val augment : Rep.item array array -> int -> Rep.move *)
(* 'augment m c' redoes the line or drops the piece for c in m *)
let augment mat c =
let l = ref row in
while !l > 0 & mat.(!l-1).(c-1) = Empty do
decr l
done;
!l

(* val conv : Graphics.status -> int *)
(* convert the region where player has clicked in controlling the game *)
let conv st =
(st.Graphics.mouse_x - 5) / 50 + 1

(* val wait_click : unit -> Graphics.status *)
(* wait for a mouse click *)
let wait_click () = Graphics.wait_next_event [Graphics.Button_down]

(* val choiceH : Rep.game -> Rep.move *)
(* give opportunity to the human player to choose a move *)
(* the function offers possible moves *)
let rec choice player game =
let c = ref 0 in
while not ( List.mem !c (legal_moves player game) ) do
c := conv ( wait_click() )
done;
!c
(* val home : unit -> unit : home screen *)
let home () =
Graphics.open_graph
(" " ^ (string_of_int width) ^ "x" ^ (string_of_int height) ^ "+50+50");
Graphics.moveto (height/2) (width/2);
Graphics.set_color cF;
Graphics.draw_string "C4";
Graphics.set_color cN;
Graphics.moveto 2 2;
Graphics.draw_string "by Romuald COEFFIER & Mathieu DESPIERRE";
ignore (wait_click ());
Graphics.clear_graph()

(* val end : unit -> unit , the end of the game *)
let exit () = Graphics.close_graph()

(* val draw_button : int -> int -> int -> int -> string -> unit *)
(* 'draw_button x y w h s' draws a rectangular button at coordinates *)
(* x,y with width w and height h and appearance s *)
let draw_button x y w h s =
Graphics.set_color cN;
Graphics.moveto x y;
Graphics.lineto x (y+h);
Graphics.lineto (x+w) (y+h);
Graphics.lineto (x+w) y;
Graphics.lineto x y;
Graphics.moveto (x+margin) (hec);
Graphics.draw_string s

(* val draw_message : string -> unit * position message s *)
let draw_message s =
Graphics.set_color cN;
Graphics.moveto lec hec;
Graphics.draw_string s

(* val erase_message : unit -> unit erase the starting position *)
let erase_message () =
Graphics.set_color Graphics.white;
Graphics.fill_rect 0 (height_of_game+1) width htexte

(* val question : string -> bool *)
(* 'question s' poses the question s, the response being obtained by *)
(* selecting one of two buttons, 'yes' (=true) and 'no' (=false) *)
let question s =
let rec attente () =
let e = wait_click () in
if (e.Graphics.mouse_y < (yb+hb)) & (e.Graphics.mouse_y > yb) then
if (e.Graphics.mouse_x > xb1) & (e.Graphics.mouse_x < (xb1+wb)) then
true
else
if (e.Graphics.mouse_x > xb2) & (e.Graphics.mouse_x < (xb2+wb)) then
false
else
attente()
else
attente () in
draw_message s;
draw_button xb1 yb wb hb "yes";
draw_button xb2 yb wb hb "no";
attente()

(* val q_begin : unit -> bool *)
(* Ask, using function 'question', if the player wishes to start *)
(* (yes=true) *)
let q_begin () =
let b = question "Would you like to begin ?" in
erase_message();
b

(* val q_continue : unit -> bool *)
(* Ask, using function 'question', if the player wishes to play again *)
(* (yes=true) *)
let q_continue () =
let b = question "Play again ?" in
erase_message();
b

let q_player () =
let b = question "Is there to be a machine player?" in
erase_message ();
b
(* val won : unit -> unit *)
(* val lost : unit -> unit *)
(* val nil : unit -> unit *)
(* Three functions for these three cases *)
let won () =
draw_message "I won :-)" ; ignore (wait_click ()) ; erase_message()
let lost () =
draw_message "You won :-("; ignore (wait_click ()) ; erase_message()
let nil () =
draw_message "Stalemate" ; ignore (wait_click ()) ; erase_message()

(* val init : unit -> unit *)
(* This is called at every start of the game for the position *)
let init = draw_table

let position b c aj nj =
if b then
draw_piece (augment nj c) c cA
else
draw_piece (augment nj c) c cB

(* val drawH : int -> Rep.item array array -> unit *)
(* Position when the human player chooses move cp in situation j *)
let drawH cp j = draw_piece (augment j cp) cp cA

(* val drawM : int -> cell array array -> unit*)
(* Position when the machine player chooses move cp in situation j *)
let drawM cp j = draw_piece (augment j cp) cp cB
end ;;
module C4_graph :
sig
type game = C4_rep.game
and move = C4_rep.move
val r : int
val ec : int
val dec : int
val cote : int
val htexte : int
val width : int
val height : int
val height_of_game : int
val hec : int
val lec : int
val margin : int
val xb1 : int
val xb2 : int
val yb : int
val wb : int
val hb : int
val t2e : int -> int
val cN : Graphics.color
val cA : Graphics.color
val cB : Graphics.color
val cF : Graphics.color
val draw_table : unit -> unit
val draw_piece : int -> int -> Graphics.color -> unit
val augment : C4_rep.cell array array -> int -> int
val conv : Graphics.status -> int
val wait_click : unit -> Graphics.status
val choice : 'a -> C4_rep.cell array array -> int
val home : unit -> unit
val exit : unit -> unit
val draw_button : int -> int -> int -> int -> string -> unit
val draw_message : string -> unit
val erase_message : unit -> unit
val question : string -> bool
val q_begin : unit -> bool
val q_continue : unit -> bool
val q_player : unit -> bool
val won : unit -> unit
val lost : unit -> unit
val nil : unit -> unit
val init : unit -> unit
val position : bool -> int -> 'a -> C4_rep.cell array array -> unit
val drawH : int -> C4_rep.cell array array -> unit
val drawM : int -> C4_rep.cell array array -> unit
end


We may also create a new skeleton (C4_skeletonG) which results from the application of parametric module FSkeleton.


# module C4_skeletonG =
FSkeleton (C4_rep) (C4_graph) (C4_eval) (FAlphabeta (C4_rep) (C4_eval)) ;;


Only the display parameter differs from the text version application of FSkeleton. We may thereby create a principal module for Connect Four with a graphical user interface.


# module C4_mainG = FMain(C4_skeletonG) ;;
module C4_mainG :
sig
val play_game : (unit -> 'a) * (unit -> 'b) -> unit
val main : unit -> unit
end


The evaluation of the expression C4_mainG.main() opens a graphical window as in figure 17.5 and controls the interaction with the user.

Stonehenge

Stonehenge, created by Reiner Knizia, is a game involving construction of ``ley-lines.'' The rules are simple to understand but our interest in the game lies in its high number of possible moves. The rules may be found at:

Link


http://www.cix.co.uk/~convivium/files/stonehen.htm


The initial game position is represented in figure 17.6.

Game Presentation

The purpose of the game is to win at least 8 ``ley-lines'' (clear lines) out of the 15 available. One gains a line by positioning pieces (or megaliths) on gray positions along a ley-line.



Figure 17.6: Initial position of Stonehenge.


In turn, each player places one of his 9 pieces, numbered from 1 to 6, on one of the 18 gray internal positions. They may not place a piece on a position that is already occupied. Each time a piece is placed, one or several ley-lines may be won or lost.

A ley-line is won by a player if the total of the values of his pieces on the line is greater than the total of the pieces for the other player. There may be empty spaces left if the opponent has no pieces left that would allow winning the line.

For example in figure 17.7, the black player starts by placing the piece of value 3, the red player his ``2'' piece, then the black player plays the ``6'' piece, winning a line.

Red then plays the ``4'' piece, also winning a ley-line. This line has not been completely filled, but red has won because there is no way for black to overcome red's score.

Note that the red player might just as well have played ``3'' rather than ``4,'' and still won the line. In effect, there is only one free case for this ley-line where the strongest black piece has a value of 5, and so black cannot beat red for this particular line.



Figure 17.7: Position after 4 moves.


In the case where the scores are equal across a full line, whoever placed the last piece without having beaten his adversary's score, loses the line. Figure 17.8 demonstrates such a situation.

The last red move is piece ``4''. On the full line where the ``4'' is placed, the scores are equal. Since red was the last player to have placed a piece, but did not beat his adversary, red loses the line, as indicated by a black block.

We may observe that the function play fills the role of arbitrating and accounting for these subtleties in the placement of lines.



Figure 17.8: Position after 6 moves.


There can never be a tie in this game. There are 15 lines, each of which will be accounted for at some point in the game, at which point one of the players will have won at least 8 lines.

Search Complexity

Before completely implementing a new game, it is important to estimate the number of legal moves between two moves in a game, as well as the number of possible moves for each side. These values may be used to estimate a reasonable maximum depth for the minimax-ab algorithm.

In the game Stonehenge, the number of moves for each side is initially based on the number of pieces for the two players, that is, 18. The number of possible moves diminishes as the game progresses. At the first move, the player has 6 different pieces and 18 positions free. At the second move, the second player has 6 different pieces, and 17 positions in which they may be placed (102 legal moves). Moving from a depth of 2 to 4 for the initial moves of the game results in the number of choices going from about 104 to about 108.

On the other hand, near the end of the game, in the final 8 moves, the complexity is greatly reduced. If we take a pessimistic calculation (where all pieces are different), we obtain about 23 million possibilities:

4*8 * 4*7 * 3*6 * 3*5 * 2*4 * 2*3 * 1*2 * 1*1 = 23224320

It might seem appropriate to calculate with a depth of around 2 for the initial set of moves. This may depend on the evaluation function, and on its ability to evaluate the positions at the start of the game, when there are few pieces in place. On the other hand, near the end of the game, the depth may readily be increased to around 4 or 6, but this would probably be too late a point to recover from a weak position.

Implementation

We jump straight into describing the game representation and arbitration so that we may concentrate on the evaluation function.

The implementation of this game follows the architecture used for Connect Four, described in figure 17.4. The two principal difficulties will be to follow the game rules for the placement of pieces, and the evaluation function, which must be able to evaluate positions as quickly as possible while remaining useful.

Game Representation.
There are four notable data structures in this game: We provide a unique number for each location:
             1---2
            / \ / \
           3---4---5
          / \ / \ / \
         6---7---8---9
        / \ / \ / \ / \
       10--11--12--13--14
        \ / \ / \ / \ /
         15--16--17--18 
Each location participates in 3 ley-lines. We also number each ley-line. This description may be found in the declaration of the list lines, which is converted to a vector (vector_l). A location is either empty, or contains a piece that has been placed, and the piece's possessor. We also store, for each location, the number of the lines that pass through it. This table is calculated by lines_per_case and is named num_line_per_case.

The game is represented by the vector of 18 cases, the vector of 15 ley-lines either won or not, and the lists of pieces left for the two players. The function game_start creates these four elements.

The calculation of a player's legal moves resolves into a Cartesian product of the pieces available against the free positions. Various utility functions allow counting the score of a player on a line, calculating the number of empty locations on a line, and verifying if a line has already been won. We only need to implement play which plays a move and decides which pieces to place. We write this function at the end of the listing of module Stone_rep.

# module Stone_rep = struct
type player = bool
type piece = P of int
let int_of_piece = function P x -> x
type placement = None | M of player
type case = Empty | Occup of player*piece
let value_on_case = function
Empty -> 0
| Occup (j, x) -> int_of_piece x

type game = J of case array * placement array * piece list * piece list
type move = int * piece

let lines = [
[0;1]; [2;3;4]; [5; 6; 7; 8;]; [9; 10; 11; 12; 13]; [14; 15; 16; 17];
[0; 2; 5; 9]; [1; 3; 6; 10; 14]; [4; 7; 11; 15]; [8; 12; 16]; [13; 17];
[9; 14]; [5; 10; 15]; [2; 6; 11; 16]; [0; 3; 7; 12; 17]; [1; 4; 8; 13] ]

let vector_l = Array.of_list lines

let lines_per_case v =
let t = Array.length v in
let r = Array.create 18 [||] in
for i = 0 to 17 do
let w = Array.create 3 0
and p = ref 0 in
for j=0 to t-1 do if List.mem i v.(j) then (w.(!p) <- j; incr p)
done;
r.(i) <- w
done;
r

let num_line_per_case = lines_per_case vector_l
let rec lines_of_i i l = List.filter (fun t -> List.mem i t) l

let lines_of_cases l =
let a = Array.create 18 l in
for i=0 to 17 do
a.(i) <- (lines_of_i i l)
done; a

let ldc = lines_of_cases lines

let game_start ()= let lp = [6; 5; 4; 3; 3; 2; 2; 1; 1] in
J ( Array.create 18 Empty, Array.create 15 None,
List.map (fun x -> P x) lp, List.map (fun x -> P x) lp )

let rec unicity l = match l with
[] -> []
| h::t -> if List.mem h t then unicity t else h:: (unicity t)

let legal_moves player (J (ca, m, r1, r2)) =
let r = if player then r1 else r2 in
if r = [] then []
else
let l = ref [] in
for i = 0 to 17 do
if value_on_case ca.(i) = 0 then l:= i:: !l
done;
let l2 = List.map (fun x->
List.map (fun y-> x,y) (List.rev(unicity r)) ) !l in
List.flatten l2
let copy_board p = Array.copy p

let carn_copy m = Array.copy m
let rec play_piece stone l = match l with
[] -> []
| x::q -> if x=stone then q
else x::(play_piece stone q)

let count_case player case = match case with
Empty -> 0
| Occup (j,p) -> if j = player then (int_of_piece p) else 0

let count_line player line pos =
List.fold_left (fun x y -> x + count_case player pos.(y)) 0 line

let rec count_max n = function
[] -> 0
| t::q ->
if (n>0) then
(int_of_piece t) + count_max (n-1) q
else
0

let rec nbr_cases_free ca l = match l with
[] -> 0
| t::q -> let c = ca.(t) in
match c with
Empty -> 1 + nbr_cases_free ca q
| _ -> nbr_cases_free ca q

let a_placement i ma =
match ma.(i) with
None -> false
| _ -> true

let which_placement i ma =
match ma.(i) with
None -> failwith "which_placement"
| M j -> j

let is_filled l ca = nbr_cases_free ca l = 0

(* function play : arbitrates the game *)
let play player move game =
let (c, i) = move in
let J (p, m, r1, r2) = game in
let nr1,nr2 = if player then play_piece i r1,r2
else r1, play_piece i r2 in
let np = copy_board p in
let nm = carn_copy m in
np.(c)<-Occup(player,i); (* on play le move *)
let lines_of_the_case = num_line_per_case.(c) in

(* calculation of the placements of the three lines *)
for k=0 to 2 do
let l = lines_of_the_case.(k) in
if not (a_placement l nm) then (
if is_filled vector_l.(l) np then (
let c1 = count_line player vector_l.(l) np
and c2 = count_line (not player) vector_l.(l) np in
if (c1 > c2) then nm.(l) <- M player
else ( if c2 > c1 then nm.(l) <- M (not player)
else nm.(l) <- M (not player ))))
done;

(* calculation of other placements *)
for k=0 to 14 do
if not (a_placement k nm ) then
if is_filled vector_l.(k) np then failwith "player"
else
let c1 = count_line player vector_l.(k) np
and c2 = count_line (not player) vector_l.(k) np in
let cases_free = nbr_cases_free np vector_l.(k) in
let max1 = count_max cases_free
(if player then nr1 else nr2)
and max2 = count_max cases_free
(if player then nr2 else nr1) in
if c1 >= c2 + max2 then nm.(k) <- M player
else if c2 >= c1 + max1 then nm.(k) <- M (not player)
done;
J(np,nm,nr1,nr2)
end ;;
module Stone_rep :
sig
type player = bool
and piece = | P of int
val int_of_piece : piece -> int
type placement = | None | M of player
and case = | Empty | Occup of player * piece
val value_on_case : case -> int
type game = | J of case array * placement array * piece list * piece list
and move = int * piece
val lines : int list list
val vector_l : int list array
val lines_per_case : int list array -> int array array
val num_line_per_case : int array array
val lines_of_i : 'a -> 'a list list -> 'a list list
val lines_of_cases : int list list -> int list list array
val ldc : int list list array
val game_start : unit -> game
val unicity : 'a list -> 'a list
val legal_moves : bool -> game -> (int * piece) list
val copy_board : 'a array -> 'a array
val carn_copy : 'a array -> 'a array
val play_piece : 'a -> 'a list -> 'a list
val count_case : player -> case -> int
val count_line : player -> int list -> case array -> int
val count_max : int -> piece list -> int
val nbr_cases_free : case array -> int list -> int
val a_placement : int -> placement array -> bool
val which_placement : int -> placement array -> player
val is_filled : int list -> case array -> bool
val play : player -> int * piece -> game -> game
end


The function play decomposes into three stages:
  1. Copying the game position and placing a move onto this position;

  2. Determination of the placement of a piece on one of the three lines of the case played;

  3. Treatment of the other ley-lines.
The second stage verifies that, of the three lines passing through the position of the move, none has already been won, and then checks if they are able to be won. In the latter case, it counts scores for each player and determines which strictly has the greatest score, and attributes the line to the appropriate player. In case of equality, the line goes to the most recent player's adversary. In effect, there are no lines with just one case. A filled line has at least two pieces. Thus if the player which just played has just matched the score of his adversary, he cannot expect to win the line which then goes to his adversary. If the line is not filled, it will be analyzed by ``stage 3.''

The third stage verifies for each line not yet attributed that it is not filled, and then checks if a player cannot be beaten by his opponent. In this case, the line is immediately given to the opponent. To perform this test, it is necessary to calculate the maximum total potential score of a player on the line (that is, by using his best pieces). If the line is still under dispute, nothing more is done.

Evaluation.
The evaluation function must remain simple due to the large number of cases to deal with near the beginning of the game. The idea is not to excessively simplify the game by immediately playing the strongest pieces which would then leave the remainder of the game open for the adversary to play his strong pieces.

We will use two criteria: the number of lines won and an estimate of the potential of future moves by calculating the value of the remaining pieces. We may use the following formula for player 1:

score   =   50 * (c1 - c2) + 10 * (pr1 - pr2)

where ci is the number of lines won, and pri is the sum of the pieces remaining for player i.

The formula returns a positive result if the differences between won lines (c1 - c2) and the potentials (pr1 - pr2) turn to the advantage of player 1. We may see thus that a placement of piece 6 is not appropriate unless it provides a win of at least 2 lines. The gain of one line provides 50, while using the ``6'' piece costs 10 × 6 points, so we would thus prefer to play ``1'' which results in the same score, namely a loss of 10 points.

# module Stone_eval = struct
open Stone_rep
type game = Stone_rep.game

exception Done of bool
let moreI = 1000 and lessI = -1000

let nbr_lines_won (J(ca, m,r1,r2)) =
let c1,c2 = ref 0,ref 0 in
for i=0 to 14 do
if a_placement i m then if which_placement i m then incr c1 else incr c2
done;
!c1,!c2

let rec nbr_points_remaining lig = match lig with
[] -> 0
| t::q -> (int_of_piece t) + nbr_points_remaining q

let evaluate player game =
let (J (ca,ma,r1,r2)) = game in
let c1,c2 = nbr_lines_won game in
let pr1,pr2 = nbr_points_remaining r1, nbr_points_remaining r2 in
match player with
true -> if c1 > 7 then moreI else 50 * (c1 - c2) + 10 * (pr1 - pr2)
| false -> if c2 > 7 then lessI else 50 * (c1 - c2) + 10 * (pr1 - pr2)

let is_leaf player game =
let v = evaluate player game in
v = moreI or v = lessI or legal_moves player game = []

let is_stable player game = true

type state = G | P | N | C
let state_of player m =
let v = evaluate player m in
if v = moreI then if player then G else P
else
if v = lessI
then if player then P else G
else
if legal_moves player m = [] then N else C
end;;
module Stone_eval :
sig
type game = Stone_rep.game
exception Done of bool
val moreI : int
val lessI : int
val nbr_lines_won : Stone_rep.game -> int * int
val nbr_points_remaining : Stone_rep.piece list -> int
val evaluate : bool -> Stone_rep.game -> int
val is_leaf : bool -> Stone_rep.game -> bool
val is_stable : 'a -> 'b -> bool
type state = | G | P | N | C
val state_of : bool -> Stone_rep.game -> state
end

# module Stone_graph = struct
open Stone_rep
type piece = Stone_rep.piece
type placement = Stone_rep.placement
type case = Stone_rep.case
type game = Stone_rep.game
type move = Stone_rep.move

(* brightness for a piece *)
let brightness = 20

(* the colors *)
let cBlack = Graphics.black
let cRed = Graphics.rgb 165 43 24
let cYellow = Graphics.yellow
let cGreen = Graphics.rgb 31 155 33 (*Graphics.green*)
let cWhite = Graphics.white
let cGray = Graphics.rgb 128 128 128
let cBlue = Graphics.rgb 196 139 25 (*Graphics.blue*)

(* width and height *)
let width = 600
let height = 500
(* the border at the top of the screen from which drawing begins *)
let top_offset = 30

(* height of foundaries *)
let bounds = 5

(* the size of the border on the left side of the virtual table *)
let virtual_table_xoffset = 145

(* left shift for the black pieces *)
let choice_black_offset = 40

(* left shift for the red pieces *)
let choice_red_offset = 560

(* height of a case for the virtual table *)
let virtual_case_size = 60

(* corresp : int*int -> int*int *)
(* establishes a correspondence between a location in the matrix *)
(* and a position on the virtual table servant for drawing *)
let corresp cp =
match cp with
0 -> (4,1)
| 1 -> (6,1)
| 2 -> (3,2)
| 3 -> (5,2)
| 4 -> (7,2)
| 5 -> (2,3)
| 6 -> (4,3)
| 7 -> (6,3)
| 8 -> (8,3)
| 9 -> (1,4)
| 10 -> (3,4)
| 11 -> (5,4)
| 12 -> (7,4)
| 13 -> (9,4)
| 14 -> (2,5)
| 15 -> (4,5)
| 16 -> (6,5)
| 17 -> (8,5)
| _ -> (0,0)

let corresp2 ((x,y) as cp) =
match cp with
(0,0) -> 0
| (0,1) -> 1
| (1,0) -> 2
| (1,1) -> 3
| (1,2) -> 4
| (2,0) -> 5
| (2,1) -> 6
| (2,2) -> 7
| (2,3) -> 8
| (3,0) -> 9
| (3,1) -> 10
| (3,2) -> 11
| (3,3) -> 12
| (3,4) -> 13
| (4,0) -> 14
| (4,1) -> 15
| (4,2) -> 16
| (4,3) -> 17
| (x,y) -> print_string "Err ";
print_int x;print_string " ";
print_int y; print_newline() ; 0

let col = 5
let lig = 5

(* draw_background : unit -> unit *)
(* draw the screen background *)
let draw_background () =
Graphics.clear_graph() ;
Graphics.set_color cBlue ;
Graphics.fill_rect bounds bounds width (height-top_offset)

(* draw_places : unit -> unit *)
(* draw the pieces at the start of the game *)
let draw_places () =
for l = 0 to 17 do
let cp = corresp l in
if cp <> (0,0) then
begin
Graphics.set_color cBlack ;
Graphics.draw_circle
((fst cp)*30 + virtual_table_xoffset)
(height - ((snd cp)*55 + 25)-50) (brightness+1) ;
Graphics.set_color cGray ;
Graphics.fill_circle
((fst cp)*30 + virtual_table_xoffset)
(height - ((snd cp)*55 + 25)-50) brightness
end

done

(* draw_force_lines : unit -> unit *)
(* draws ley-lines *)
let draw_force_lines () =
Graphics.set_color cYellow ;
let lst = [((2,1),(6,1)); ((1,2),(7,2)); ((0,3),(8,3));
((-1,4),(9,4)); ((0,5),(8,5)); ((5,0),(1,4));
((7,0),(2,5)); ((8,1),(4,5)); ((9,2),(6,5));
((10,3),(8, 5)); ((3,6),(1,4)); ((5,6),(2,3));
((7,6),(3,2)); ((9,6),(4,1)); ((10,5),(6,1))] in
let rec lines l =
match l with
[] -> ()
| h::t -> let deb = fst h and complete = snd h in
Graphics.moveto
((fst deb) * 30 + virtual_table_xoffset)
(height - ((snd deb) * 55 + 25) -50) ;
Graphics.lineto
((fst complete) * 30 + virtual_table_xoffset)
(height - ((snd complete) * 55 + 25) -50) ;
lines t
in lines lst

(* draw_final_places : unit -> unit *)
(* draws final cases for each ley-line *)
(* coordinates represent in the virtual array
used for positioning *)

let draw_final_places () =
let lst = [(2,1); (1,2); (0,3); (-1,4); (0,5); (3,6); (5,6);
(7,6); (9,6); (10,5); (10,3); (9,2); (8,1); (7,0);
(5,0)] in
let rec final l =
match l with
[] -> ()
| h::t -> Graphics.set_color cBlack ;
Graphics.draw_circle
((fst h)*30 + virtual_table_xoffset)
(height - ((snd h)*55 + 25)-50) (brightness+1) ;
Graphics.set_color cGreen ;
Graphics.fill_circle
((fst h)*30 + virtual_table_xoffset)
(height - ((snd h)*55 + 25)-50) brightness ;
final t
in final lst


(* draw_table : unit -> unit *)
(* draws the whole game *)
let draw_table () =
Graphics.set_color cYellow ;
draw_background () ;
Graphics.set_line_width 5 ;
draw_force_lines () ;
Graphics.set_line_width 2 ;
draw_places () ;
draw_final_places ();
Graphics.set_line_width 1

(* move -> couleur -> unit *)
let draw_piece player (n_case,P cp) = (* (n_caOccup(c,v),cp) col =*)
Graphics.set_color (if player then cBlack else cRed); (*col;*)
let co = corresp n_case in
let x = ((fst co)*30 + 145) and y = (height - ((snd co)*55 + 25)-50) in
Graphics.fill_circle x y brightness ;
Graphics.set_color cWhite ;
Graphics.moveto (x - 3) (y - 3) ;
let dummy = 5 in
Graphics.draw_string (string_of_int cp) (*;*)
(* print_string "---";print_int n_case; print_string " "; print_int cp ;print_newline() *)

(* conv : Graphics.status -> int *)
(* convert a mouse click into a position on a virtual table permitting *)
(* its drawing *)
let conv st =
let xx = st.Graphics.mouse_x and yy = st.Graphics.mouse_y in
let y = (yy+10)/virtual_case_size - 6 in
let dec =
if y = ((y/2)*2) then 60 else 40 in
let offset = match (-1*y) with
0 -> -2
| 1 -> -1
| 2 -> -1
| 3 -> 0
| 4 -> -1
| _ -> 12 in
let x = (xx+dec)/virtual_case_size - 3 + offset in
(-1*y, x)

(* line_number_to_aff : int -> int*int *)
(* convert a line number into a polition on the virtual table serving *)
(* for drawing *)
(* the coordinate returned corresponds to the final case for the line *)
let line_number_to_aff n =
match n with
0 -> (2,1)
| 1 -> (1,2)
| 2 -> (0,3)
| 3 -> (-1,4)
| 4 -> (0,5)
| 5 -> (5,0)
| 6 -> (7,0)
| 7 -> (8,1)
| 8 -> (9,2)
| 9 -> (10,3)
| 10 -> (3,6)
| 11 -> (5,6)
| 12 -> (7,6)
| 13 -> (9,6)
| 14 -> (10,5)
| _ -> failwith "line" (*raise Rep.Out_of_bounds*)

(* draw_lines_won : game -> unit *)
(* position a marker indicating the player which has taken the line *)
(* this is done for all lines *)
let drawb l i =
match l with
None -> failwith "draw"
| M j -> let pos = line_number_to_aff i in
(* print_string "''''";
print_int i;
print_string "---";
Printf.printf "%d,%d\n" (fst pos) (snd pos);
*) Graphics.set_color (if j then cBlack else cRed);
Graphics.fill_rect ((fst pos)*30 + virtual_table_xoffset-bounds)
(height - ((snd pos)*55 + 25)-60) 20 40

let draw_lines_won om nm =
for i=0 to 14 do
if om.(i) <> nm.(i) then drawb nm.(i) i
done
(*********************
let black_lines = Rep.lines_won_by_player mat Rep.Noir and
red_lines = Rep.lines_won_by_player mat Rep.Rouge
in
print_string "black : "; print_int (Rep.list_size black_lines);
print_newline () ;
print_string "red : "; print_int (Rep.list_size red_lines);
print_newline() ;

let rec draw l col =
match l with
[] -> ()
| h::t -> let pos = line_number_to_aff h in
Graphics.set_color col ;
Graphics.fill_rect ((fst pos)*30 + virtual_table_xoffset-bounds)
(height - ((snd pos)*55 + 25)-60) 20 40 ;
draw t col
in draw black_lines cBlack ;
draw red_lines cRed
***************************************************)

(* draw_poss : item list -> int -> unit *)
(* draw the pieces available for a player based on a list *)
(* the parameter "off" indicates the position at which to place the list *)
let draw_poss player lst off =
let c = ref (1) in
let rec draw l =
match l with
[] -> ()
| v::t -> if player then Graphics.set_color cBlack
else Graphics.set_color cRed;
let x = off and
y = 0+(!c)*50 in
Graphics.fill_circle x y brightness ;
Graphics.set_color cWhite ;
Graphics.moveto (x - 3) (y - 3) ;
Graphics.draw_string (string_of_int v) ;
c := !c + 1 ;
draw t

in draw (List.map (function P x -> x) lst)

(* draw_choice : game -> unit *)
(* draw the list of pieces still available for each player *)
let draw_choice (J (ca,ma,r1,r2)) =
Graphics.set_color cBlue ;
Graphics.fill_rect (choice_black_offset-30) 10 60
(height - (top_offset + bounds)) ;
Graphics.fill_rect (choice_red_offset-30) 10 60
(height - (top_offset + bounds)) ;
draw_poss true r1 choice_black_offset ;
draw_poss false r2 choice_red_offset

(* wait_click : unit -> unit *)
(* wait for a mouse click *)
let wait_click () = Graphics.wait_next_event [Graphics.Button_down]


(* item list -> item *)
(* return, for play, the piece chosen by the user *)
let select_pion player lst =
let ok = ref false and
choice = ref 99 and
pion = ref (P(-1))
in
while not !ok do
let st = wait_click () in
let size = List.length lst in
let x = st.Graphics.mouse_x and y = st.Graphics.mouse_y in
choice := (y+25)/50 - 1 ;
if !choice <= size && ( (player && x < 65 )
|| ( (not player) && (x > 535))) then ok := true
else ok := false ;
if !ok then
try
pion := (List.nth lst !choice) ;
Graphics.set_color cGreen ;
Graphics.set_line_width 2 ;
Graphics.draw_circle
(if player then choice_black_offset else choice_red_offset)
((!choice+1)*50) (brightness + 1)
with _ -> ok := false ;
done ;
!pion

(* choiceH : game -> move *)
(* return a move for the human player.
return the choice of the number, the case, and the piece *)
let rec choice player game = match game with (J(ca,ma,r1,r2)) ->
let choice = ref (P(-1))
and c = ref (-1, P(-1)) in
let lcl = legal_moves player game in
while not (List.mem !c lcl) do
print_newline();print_string "CHOICE";
List.iter (fun (c,P p) -> print_string "["; print_int c;print_string " ";
print_int p;print_string "]")
(legal_moves player game);
draw_choice game;
choice := select_pion player (if player then r1 else r2) ;
(* print_string "choice "; print_piece !choice;*)
c := (corresp2 (conv (wait_click())), !choice)
(* let (x,y) = !c in
(print_string "...";print_int x; print_string " "; print_piece y;
print_string " -> ";
print_string "END_CHOICE";print_newline())
*) done ;
!c (* case, piece *)


(* home : unit -> unit *)
(* place a message about the game *)
let home () =
Graphics.open_graph
(" " ^ (string_of_int (width + 10)) ^ "x" ^ (string_of_int (height + 10))
^ "+50+50") ;
Graphics.moveto (height / 2) (width / 2) ;
Graphics.set_color cBlue ;
Graphics.draw_string "Stonehenge" ;
Graphics.set_color cBlack ;
Graphics.moveto 2 2 ;
Graphics.draw_string "Mixte Projets Maîtrise & DESS GLA" ;
wait_click () ;
Graphics.clear_graph ()

(* exit : unit -> unit *)
(* close everything ! *)
let exit () =
Graphics.close_graph ()

(* draw_button : int -> int -> int -> int -> string -> unit *)
(* draw a button with a message *)
let draw_button x y w h s =
Graphics.set_line_width 1 ;
Graphics.set_color cBlack ;
Graphics.moveto x y ;
Graphics.lineto x (y+h) ;
Graphics.lineto (x+w) (y+h) ;
Graphics.lineto (x+w) y ;
Graphics.lineto x y ;
Graphics.moveto (x+bounds) (height - (top_offset/2)) ;
Graphics.draw_string s

(* draw_message : string -> unit *)
(* position a message *)
let draw_message s =
Graphics.set_color cBlack;
Graphics.moveto 3 (height - (top_offset/2)) ;
Graphics.draw_string s

(* erase_message : unit -> unit *)
(* as the name indicates *)
let erase_message () =
Graphics.set_color Graphics.white;
Graphics.fill_rect 0 (height-top_offset+bounds) width top_offset

(* question : string -> bool *)
(* pose the user a question, and wait for a yes/no response *)
let question s =
let xb1 = (width/2) and xb2 = (width/2 + 30) and wb = 25 and hb = 16
and yb = height - 20 in
let rec attente () =
let e = wait_click () in
if (e.Graphics.mouse_y < (yb+hb)) & (e.Graphics.mouse_y > yb) then
if (e.Graphics.mouse_x > xb1) & (e.Graphics.mouse_x < (xb1+wb)) then
true
else
if (e.Graphics.mouse_x > xb2) & (e.Graphics.mouse_x < (xb2+wb)) then
false
else
attente()
else
attente () in
draw_message s;
draw_button xb1 yb wb hb "yes";
draw_button xb2 yb wb hb "no";
attente()

(* q_begin : unit -> bool *)
(* Ask if the player wishes to be the first player or not *)
let q_begin () =
let b = question "Would you like to play first ?" in
erase_message();
b

(* q_continue : unit -> bool *)
(* Ask if the user wishes to play the game again *)
let q_continue () =
let b = question "Play again ?" in
erase_message();
b
(* won : unit -> unit *)
(* a message indicating the machine has won *)
let won () = draw_message "I won :-)"; wait_click(); erase_message()

(* lost : unit -> unit *)
(* a message indicating the machine has lost *)
let lost () = draw_message "You won :-("; wait_click(); erase_message()

(* nil : unit -> unit *)
(* a message indicating stalemate *)
let nil () = draw_message "Stalemate"; wait_click(); erase_message()

(* init : unit -> unit *)
(* draw the initial game board *)
let init () = let game = game_start () in
draw_table () ;
draw_choice game

(* drawH : move -> game -> unit *)
(* draw a piece for the human player *)
(* let drawH cp j = draw_piece cp cBlack ;
draw_lines_won j
*)
(* drawM : move -> game -> unit *)
(* draw a piece for the machine player *)
(* let drawM cp j = draw_piece cp cRed ;
draw_lines_won j
*)
let print_placement m = match m with
None -> print_string "None "
| M j -> print_string ("Pl "^(if j then "1 " else "2 "))

let position player move
(J(ca1,m1,r11,r12))
(J(ca2,m2,r21,r22) as new_game) =
draw_piece player move;
draw_choice new_game;
(* print_string "_______OLD___________________\n";
Array.iter print_placement m1; print_newline();
List.iter print_piece r11; print_newline();
List.iter print_piece r12; print_newline();
print_string "_______NEW___________________\n";
Array.iter print_placement m2; print_newline();
List.iter print_piece r21; print_newline();
List.iter print_piece r22; print_newline();
*) draw_lines_won m1 m2

(*
if player then draw_piece move cBlack
else draw_piece move cRed
*)
let q_player () =
let b = question "Is there a machine playing?" in
erase_message ();
b
end;;
Characters 11114-11127:
Warning: this expression should have type unit.
Characters 13197-13209:
Warning: this expression should have type unit.
Characters 13345-13357:
Warning: this expression should have type unit.
Characters 13478-13490:
Warning: this expression should have type unit.
module Stone_graph :
sig
type piece = Stone_rep.piece
and placement = Stone_rep.placement
and case = Stone_rep.case
and game = Stone_rep.game
and move = Stone_rep.move
val brightness : int
val cBlack : Graphics.color
val cRed : Graphics.color
val cYellow : Graphics.color
val cGreen : Graphics.color
val cWhite : Graphics.color
val cGray : Graphics.color
val cBlue : Graphics.color
val width : int
val height : int
val top_offset : int
val bounds : int
val virtual_table_xoffset : int
val choice_black_offset : int
val choice_red_offset : int
val virtual_case_size : int
val corresp : int -> int * int
val corresp2 : int * int -> int
val col : int
val lig : int
val draw_background : unit -> unit
val draw_places : unit -> unit
val draw_force_lines : unit -> unit
val draw_final_places : unit -> unit
val draw_table : unit -> unit
val draw_piece : bool -> int * Stone_rep.piece -> unit
val conv : Graphics.status -> int * int
val line_number_to_aff : int -> int * int
val drawb : Stone_rep.placement -> int -> unit
val draw_lines_won :
Stone_rep.placement array -> Stone_rep.placement array -> unit
val draw_poss : bool -> Stone_rep.piece list -> int -> unit
val draw_choice : Stone_rep.game -> unit
val wait_click : unit -> Graphics.status
val select_pion : bool -> Stone_rep.piece list -> Stone_rep.piece
val choice : bool -> Stone_rep.game -> int * Stone_rep.piece
val home : unit -> unit
val exit : unit -> unit
val draw_button : int -> int -> int -> int -> string -> unit
val draw_message : string -> unit
val erase_message : unit -> unit
val question : string -> bool
val q_begin : unit -> bool
val q_continue : unit -> bool
val won : unit -> unit
val lost : unit -> unit
val nil : unit -> unit
val init : unit -> unit
val print_placement : Stone_rep.placement -> unit
val position :
bool ->
int * Stone_rep.piece -> Stone_rep.game -> Stone_rep.game -> unit
val q_player : unit -> bool
end


Assembly.
We thus write module Stone_graph which describes a graphical interface compatible with signature DISPLAY. We construct Stone_skeletonG similar to C4_skeletonG, passing in the arguments appropriate for the Stonehenge game, applying the parametric module FSkeleton.


# module Stone_skeletonG = FSkeleton (Stone_rep)
(Stone_graph)
(Stone_eval)
(FAlphabeta (Stone_rep) (Stone_eval)) ;;
module Stone_skeletonG :
sig
val depth : int ref
exception Won
exception Lost
exception Nil
val won : unit -> unit
val lost : unit -> unit
val nil : unit -> unit
val again : unit -> bool
val play_game : Stone_graph.game ref
val exit : unit -> unit
val home : unit -> unit
val playH : bool -> unit -> unit
val playM : bool -> unit -> unit
val init : unit -> (unit -> unit) * (unit -> unit)
end


We may thus construct the principal module Stone_mainG.

# module Stone_mainG = FMain(Stone_skeletonG) ;;
module Stone_mainG :
sig
val play_game : (unit -> 'a) * (unit -> 'b) -> unit
val main : unit -> unit
end


Launching Stone_mainG.main () opens the window shown in figure 17.6. After displaying a dialogue to show who is playing, the game begins. A human player will select a piece and place it.

To Learn More

This organization of these applications involves using several parametric modules that permit direct reuse of FAlphabeta and FSkeleton for the two games we have written. With Stonehenge, some of the functions from Stone_rep, needed for play, which do not appear in REPRESENTATION, are used by the evaluation function. That is why the module Stone_rep was not closed immediately by REPRESENTATION. This partitioning of modules for the specific aspects of games allows incremental development without making the game schema dependencies (presented in figure 17.4) fragile.

A first enhancement involves games where given a position and a move, it is easy to determine the preceding position. In such cases, it may be more efficient to not bother making a copy of the game for function play, but rather to conserve a history of moves played to allow backtracking. This is the case for Connect 4, but not for Stonehenge.

A second improvement is to capitalize on a player's response time by evaluating future positions while the other player is selecting his next move. For this, one may use threads (see chapter 19), which allow concurrent calculation. If the player's response is one that has already been explored, the gain in time will be immediate, if not we must start again from the new position.

A third enhancement is to build and exploit dictionaries of opening moves. We have been able to do so with Stonehenge, but it is also useful for many other games where the set of legal moves to explore is particularly large and complex at the start of the game. There is much to be gained from estimating and precalculating some ``best'' moves from the starting positions and retaining them in some sort of database. One may add a bit of ``spice'' (and perhaps unpredictability) to the games by introducing an element of chance, by picking randomly from a set of moves with similar or identical values.

A fourth view is to not limit the search depth to a fixed depth value, but rather to limit the search by a calculation time period that is not to be exceeded. In this manner, the program will be able to efficiently search to deeper depths when the number of remaining moves becomes limited. This modification requires slight modification to minmax in order to be able to re-examine a tree to increase its depth.

A game-dependent heuristic, parameterized by minmax, may be to choose which branches in the search should be pursued and which may be quickly abandoned.

There are also many other games that require little more than to be implemented or reimplemented. We might cite many classic games: Checkers, Othello, Abalone, ..., but also many lesser-known games that are, nevertheless, readily playable by computer. You may find on the web various student projects including Checkers or the game Nuba.

Link


http://www.gamecabinet.com/rules/Nuba.html


Games with stochastic qualities, such as card games and dice games, necessitate a modification of the minimax-ab algorithm in order to take account of the probabilities of the selections.

We will return to the interfaces of games in chapter 21 in constructing web-based interfaces, providing without further cost the ability to return to the last move. This also allows further benefits from the modular organization that allows modifying no more than just an element, here the game state and interactions, to extend the functionality to support two player games.




Previous Contents Next