９ｘ９の盤面に8種類のコマが自分と相手の分あって、あとは空だから
81**(8*2+1) で、ルールの制約があるからこれよりもっと少ないと思う
http://www.google.co.jp/search?hl=ja&rlz=1T4GFRD_ja___JP238&q=81**%288*2%2B1%29&btnG=%E6%A4%9C%E7%B4%A2&lr=

それまでの手がどうであってもルール上許される配置のどれかになる
でルール上許される全ての局面に評価値をつける

勝敗が微妙な局面もあるけど、そこから
自分の勝ちの局面に少ない手で到達できるとか
相手の打ち方によらず確実に勝ち局面に到達できる手とか
があるほど評価値を高くするって案はどう？