Commits

Anonymous committed 24f9e3d

lazy tree building to take full advantage of alphabeta pruning

Comments (0)

Files changed (1)

mills/ai_alphabeta.ml

   | Capture i -> Printf.sprintf "capture %d" i
   | Init -> "init move"
 
-type node = Node of state * move * node list (* state, move, children *)
+type node = Node of state * move * node lazy_t list (* state, move, children *)
 
 let string_of_node = function
   | Node (_, move, _) -> "Node(_, " ^ (string_of_move move) ^ ", _)"
     let children = List.map aux (capturables state opponent) in
     Node (state, last_move, children)
   in
-  if can_capture state last_move then build_capture ()
-  else if depth <= 0 then Node (state, last_move, [])
-  else if can_put state then build_put ()
-  else if can_fly state then build_fly ()
-  else build_move ()
+  if can_capture state last_move then Lazy.lazy_from_fun build_capture
+  else if depth <= 0 then lazy (Node (state, last_move, []))
+  else if can_put state then Lazy.lazy_from_fun build_put
+  else if can_fly state then Lazy.lazy_from_fun build_fly
+  else Lazy.lazy_from_fun build_move
+
+let force_count = ref 0
+let force thunk = 
+  incr force_count;
+  Lazy.force thunk
+  
+let print_force_stat () = Printf.eprintf "force called %d times\n%!" !force_count
+let reset_force () = force_count := 0  
+
+let force_tree root =
+  let rec f node = match force node with
+      Node (state, move, list) ->
+        List.iter f list
+  in
+  f root
 
 let print_tree root =
   let rec indent depth =
     if depth > 0 then (Printf.printf "+"; indent (pred depth))
   in
-  let rec p depth = function
+  let rec p depth node = match force node with
       Node (state, move, list) ->
         indent depth;
         Printf.printf "%s\n" (string_of_move move);
   p 0 root
 
 let count_positions node =
-  let rec count node = match node with
+  let rec count node = match force node with
     | Node (_, _, []) -> 1
     | Node (_, _, children) ->
         let counts = List.map count children in
     in
     loop alpha lst
   in
-  match node with
+  match force node with
   | Node (s, move, []) -> heuristic s
   | Node (s, move, children) ->
       if (get_turn s) mod 2 = 0 then min_score children
 
 let player =
   let find_best state lastmove depth playouts =
+    reset_force ();
     let root = build state lastmove depth in
-    let positions = count_positions root in
-    let nplayouts = playouts / positions in
-    let children = match root with Node (_, _, c) -> c in
-    let scores = List.map (score (estimate_hybrid nplayouts)) children in
+(*    force_tree root;    *)
+(*    print_force_stat ();*)
+    reset_force ();
+(*    let positions = count_positions root in*)
+(*    let nplayouts = playouts / positions in*)
+    let children = match force root with Node (_, _, c) -> c in
+    let scores = List.map (score (estimate_basic)) children in
     let better = if (get_turn state) mod 2 = 0 then (<) else (>) in
     let init = if (get_turn state) mod 2 = 0 then max_int else min_int in
     let rec select nodes scores selected score =
         if better s score then select (List.tl nodes) (List.tl scores) n s
         else select (List.tl nodes) (List.tl scores) selected score
     in
-    select children scores (Node (state, lastmove, [])) init
+    let thunk = select children scores (lazy (Node (state, lastmove, []))) init
+    in 
+    print_force_stat ();
+    force thunk    
   in
   
   object (self)
     val mutable last_move = Init
     
     method put state =
-      let selected = find_best state Init 2 15000 in
+      let selected = find_best state Init 3 15000 in
       match selected with
       | Node(_, Put i, _) -> last_move <- Put i ; i
       | _ -> failwith "no put found"
     method move state =
-      let selected = find_best state Init 4 30000 in
+      let before = Unix.gettimeofday() in
+      let selected = find_best state Init 6 30000 in      
+      let after = Unix.gettimeofday() in
+      Printf.printf "time: %f\n%!" (after -. before);
       match selected with
       | Node(_, Move (f, g), _) -> last_move <- Move (f, g) ; f, g
       | _ -> failwith "no move found"
     method fly state =
-      let selected = find_best state Init 3 30000 in
+      let selected = find_best state Init 6 30000 in
       match selected with
       | Node(_, Fly (f, g), _) -> last_move <- Fly (f, g) ; f, g
       | _ -> failwith "no fly found"
     method capture state =
       end_of_turn state; (* unrolled later *)
-      let selected = find_best state last_move 2 10000 in
+      let selected = find_best state last_move 4 10000 in
       match selected with
       | Node(_, Capture i, _) -> last_move <- Capture i ; i
       | _ -> failwith "no capture found"
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.