Ecrire un morpion en caml

Bonjour, je suis en première année de prépa maths et je suis l'option info, pour mes TIPE j'essaie de créer un jeu de morpion et j'ai pas mal avancé mais mon problème c'est bien entendu la fonction d'évaluation.
Je me suis pas mal renseigné sur l'algorithme min max et j'ai bien compris son fonctionnement. Le problème c'est qu'il sert a explorer un arbre et a en ressortir le coup le plus intéressant mais pour cet arbre justement, doit-on le créer entièrement avant de pouvoir faire quoi que ce soit ou y-a-t-il un autre moyen plus rapide?
parce que la pour le morpion ça va déjà être très long a faire mais en plus je compte étendre le programme pour faire ensuite un puissance 4 donc la l'arbre serais bien trop grand pour être réalisé a l'avance.

merci d'avance pour vos réponses.



EDIT: j'allais oublier, voici le programme que j'ai écrit:

type pion = X | O | V ;;
type gamer = joueur | ordi;;
type message= ordi_gagne | joueur_gagne | aucun_gagnant;;
exception case_non_vide ;;
let gagnant = [ (0 , 1 , 2) ; (3 , 4 , 5 ) ;(6 , 7, 8) ;(0 , 3 , 6 ) ;( 1 , 4 , 7 ) ;( 2 ,5 , 8 ) ;(1, 4 , 8 ) ;( 2 ,4 , 6 ) ] ;;
# open "graphics" ;;
let centres = [| (118,650) ; (218,650) ; (318,650) ; (118, 550) ; (218,550) ; (318,550) ; (118,450) ; (218,450) ; (318,450) |] ;;
let t=[|V;V;V;V;V;V;V;V;V|];;


let BIGMORP tab =

(*******************************************************************)
(*************************definitions*******************************)
(*******************************************************************)
open_graph "highest";
moveto 68 600;
lineto 368 600;
moveto 68 500;
lineto 368 500;
moveto 168 400;
lineto 168 700;
moveto 268 400;
lineto 268 700;
let t=ref tab in
let dessiner_croix (a,b) =
moveto (a-24) (b+24);
lineto (a+24) (b-24);
moveto (a-24) (b-24);
lineto (a+24) (b+24); in
let dessiner_rond (a,b) =
draw_circle a b 34 ; in
let dessiner a b =
match b with
| ordi -> dessiner_croix centres.(a)
| joueur -> dessiner_rond centres.(a) ; in
let place c a b t =
!t.(a)<-c;
dessiner a b; in
let jouer a b =
if !t.(a) <> V then raise case_non_vide
else
match b with
|ordi -> place X a b t;
|joueur -> place O a b t; in
let qui_gagne (a,b,c) =
match (!t.(a),!t.(b),!t.(c)) with
| X , X , X -> ordi_gagne
| O , O , O -> joueur_gagne
| _ -> aucun_gagnant ; in
let case_vide t =
let compt = ref 0 in
while !compt<=8 & (!t.(!compt)<>V) do compt := !compt+1 done;
if !compt=9 then false
else true; in
let coord2case n =
let a = fst (!n) in
let m=ref 0 and p=ref 0 in
if 168<a & a<268 then m:=1
else if 268<a & a<368 then m:=2;
let b = snd (!n) in
if 400<b & b<500 then p:=2
else if 500<b & b<600 then p:=1;
!m + 3 * !p; in
let n = ref (0,0) in
(*******************************************************************)
(****************************partie********************************)
(*******************************************************************)
while case_vide t = true do
while (button_down()=false) do done;
n:=mouse_pos();
jouer (coord2case n) joueur ;
if (mem joueur_gagne (map qui_gagne gagnant)) = true then draw_string "YOU WIN"
else if case_vide t = false then draw_string "PAS DE GAGNANT"
else let x = ref (random__int 9) in
while !t.(!x)<> V do x:= (random__int 9) done;
jouer !x ordi ;
if (mem ordi_gagne (map qui_gagne gagnant)) = true then draw_string "YOU LOOSE"
done;;






par contre, il ne fonctionne pas encore correctement, il me renvoie toujours l'exeption non rattrapée case non vide alors qu'il joue quand même le premier tour, je ne comprend pas pourquoi alors si vous avez des idées la dessus, elles sont les bienvenues ^_^