;;;; -*- Mode: Lisp; Syntax: Common-Lisp -*- ;;;; Code from Paradigms of AI Programming ;;;; Copyright (c) 1991 Peter Norvig (print-board (initial-board)) 1 2 3 4 5 6 7 8 [@=2 O=2 (+0)] 10 . . . . . . . . 20 . . . . . . . . 30 . . . . . . . . 40 . . . O @ . . . 50 . . . @ O . . . 60 . . . . . . . . 70 . . . . . . . . 80 . . . . . . . . (write (initial-board) :array t) #(3 3 3 3 3 3 3 3 3 3 3 0 0 0 0 0 0 0 0 3 3 0 0 0 0 0 0 0 0 3 3 0 0 0 0 0 0 0 0 3 3 0 0 0 2 1 0 0 0 3 3 0 0 0 1 2 0 0 0 3 3 0 0 0 0 0 0 0 0 3 3 0 0 0 0 0 0 0 0 3 3 0 0 0 0 0 0 0 0 3 3 3 3 3 3 3 3 3 3 3) # (othello (maximizer #'weighted-squares) (maximizer #'count-difference) nil) (othello (maximizer #'count-difference) (maximizer #'weighted-squares) nil) (othello (minimax-searcher 3 #'count-difference) (maximizer #'count-difference)) ... The game is over. Final result: 1 2 3 4 5 6 7 8 [@=53 O=0 (+53)] 10 @ @ @ @ @ @ @ @ 20 @ @ @ @ @ @ @ @ 30 @ @ @ @ @ @ @ @ 40 @ @ @ @ @ @ @ @ 50 @ @ @ @ @ @ @ @ 60 . . @ @ @ @ @ @ 70 . . . @ @ @ @ @ 80 . . . . @ @ . . 53 ;;; The following should produce the same result, but faster (othello (alpha-beta-searcher 3 #'count-difference) (maximizer #'count-difference)) ;;; ============================== (othello (alpha-beta-searcher 4 #'count-difference) (alpha-beta-searcher 4 #'weighted-squares)) 1 2 3 4 5 6 7 8 [@=20 O=1 (+19)] 10 O @ . . . . . . 20 . @ . . . @ @ . 30 @ @ @ @ @ @ . . 40 . @ . @ @ . . . 50 @ @ @ @ @ @ . . 60 . @ . . . . . . 70 . . . . . . . . 80 . . . . . . . . ;;; ============================== 1 2 3 4 5 6 7 8 [@=32 O=15 (+17)] 10 O O O O @ @ O O 20 @ @ O @ @ @ @ @ 30 @ @ O O @ O @ @ 40 O O @ @ @ @ @ @ 50 @ O @ @ @ @ . . 60 @ @ O @ @ O . . 70 @ . . @ @ . . . 80 . . . . . . . . 1 2 3 4 5 6 7 8 [@=34 O=19 (+15)] 10 O O O O @ @ O O 20 @ @ O @ @ @ @ @ 30 @ @ O O @ O @ @ 40 O @ O @ @ @ @ @ 50 O @ O @ @ @ @ . 60 O @ O @ @ @ . . 70 O @ @ @ @ . . . 80 O @ O . . . . . ;;; ============================== 1 2 3 4 5 6 7 8 [@=31 O=30 (+1)] 10 O O O O @ @ O O 20 @ @ O O @ @ @ O 30 @ @ O O O @ @ O 40 O @ O O O @ @ O 50 O @ O @ O @ @ O 60 O @ O @ @ @ @ O 70 O @ @ @ @ @ O O 80 O @ @ @ . . . O O moves to 85. 1 2 3 4 5 6 7 8 [@=23 O=39 (-16)] 10 O O O O @ @ O O 20 @ @ O O @ @ @ O 30 @ @ O O O @ @ O 40 O @ O O O @ @ O 50 O @ O @ O @ @ O 60 O @ O @ O @ O O 70 O @ @ O O O O O 80 O O O O O . . O @ moves to 86. 1 2 3 4 5 6 7 8 [@=26 O=37 (-11)] 10 O O O O @ @ O O 20 @ @ O O @ @ @ O 30 @ @ O O O @ @ O 40 O @ O O O @ @ O 50 O @ O @ O @ @ O 60 O @ O @ O @ O O 70 O @ @ O @ @ O O 80 O O O O O @ . O O moves to 87. The game is over. Final result: 1 2 3 4 5 6 7 8 [@=24 O=40 (-16)] 10 O O O O @ @ O O 20 @ @ O O @ @ @ O 30 @ @ O O O @ @ O 40 O @ O O O @ @ O 50 O @ O @ O @ @ O 60 O @ O @ O @ O O 70 O @ @ O @ O O O 80 O O O O O O O O -16 (othello (alpha-beta-searcher 6 #'count-difference) (alpha-beta-searcher 4 #'weighted-squares)) ;;; ============================== 1 2 3 4 5 6 7 8 [@=21 O=8 (+13)] 10 . . @ @ @ @ @ . 20 . @ . @ O @ . . 30 O @ @ O @ O O . 40 . @ . @ O @ O . 50 . @ @ @ @ @ . . 60 . @ . @ . O . . 70 . . . . . . . . 80 . . . . . . . . ;;; ============================== 1 2 3 4 5 6 7 8 [@=34 O=11 (+23)] 10 O . @ @ @ @ @ . 20 . O O @ @ @ . . 30 O @ O O @ @ @ @ 40 @ @ @ @ O @ @ . 50 @ @ @ @ @ O @ . 60 @ @ @ @ @ @ O O 70 @ . . @ . . @ O 80 . . . . . . . . ;;; ============================== 1 2 3 4 5 6 7 8 [@=23 O=27 (-4)] 10 O O O O O O O O 20 @ @ O @ @ @ . . 30 O @ O O @ @ @ @ 40 O @ O @ O @ @ . 50 O @ O @ @ O @ . 60 O O O @ @ @ O O 70 O . O @ . . @ O 80 O . . . . . . . ;;; ============================== 1 2 3 4 5 6 7 8 [@=24 O=40 (-16)] 10 O O O O O O O O 20 @ @ O @ O O @ @ 30 O @ O O @ @ @ @ 40 O @ O O @ @ @ O 50 O O @ @ O @ O O 60 O O O @ O @ @ O 70 O O O O @ @ O O 80 O O O O O @ @ O -16 ;;; ============================== 1 2 3 4 5 6 7 8 [@=20 O=1 (+19)] 10 O @ . . . . . . 20 . @ . . . @ @ . 30 @ @ @ @ @ @ . . 40 . @ . @ @ . . . 50 @ @ @ @ @ @ . . 60 . @ . . . . . . 70 . . . . . . . . 80 . . . . . . . . ;;; ============================== ;;; Using modified-weighted-squares 1 2 3 4 5 6 7 8 [@=42 O=21 (+21)] 10 @ @ @ @ @ @ @ @ 20 @ @ O O O O @ @ 30 @ O @ @ @ @ O @ 40 @ O @ @ @ @ O @ 50 @ O @ O @ @ O @ 60 @ @ O @ O @ @ @ 70 @ O @ @ @ @ @ @ 80 O O O O O O O . ;;; ============================== (othello-series (alpha-beta-searcher 2 #'modified-weighted-squares) (alpha-beta-searcher 2 #'weighted-squares) 5) 0 60 (-28 40 -28 40 -28 40 -28 40 -28 40) (random-othello-series (alpha-beta-searcher 2 #'weighted-squares) (alpha-beta-searcher 2 #'modified-weighted-squares) 5) 4 -76 (-8 -40 22 -30 10 -10 12 -18 4 -18) > (round-robin (list (maximizer #'count-difference) (maximizer #'mobility) (maximizer #'weighted-squares) (maximizer #'modified-weighted-squares) #'random-strategy) 5 10 '(count-difference mobility weighted modified-weighted random)) COUNT-DIFFERENCE 12.5: --- 3.0 2.5 0.0 7.0 MOBILITY 20.5: 7.0 --- 1.5 5.0 7.0 WEIGHTED 28.0: 7.5 8.5 --- 3.0 9.0 MODIFIED-WEIGHTED 31.5: 10.0 5.0 7.0 --- 9.5 RANDOM 7.5: 3.0 3.0 1.0 0.5 --- ;;; ============================== > (round-robin (list (alpha-beta-searcher 4 #'count-difference) (alpha-beta-searcher 4 #'weighted-squares) (alpha-beta-searcher 4 #'modified-weighted-squares) #'random-strategy) 5 10 '(count-difference weighted modified-weighted random)) COUNT-DIFFERENCE 12.0: --- 2.0 0.0 10.0 WEIGHTED 23.5: 8.0 --- 5.5 10.0 MODIFIED-WEIGHTED 24.5: 10.0 4.5 --- 10.0 RANDOM 0.0: 0.0 0.0 0.0 --- ;;; ==============================