実は、中間評価関数を使った簡単な次の一手を出す部分はすぐに作ってしまいました。これの詳細は後日だします。
今日は、とりあえず動いた完全読み切りの部分です。完全読み切りとは、ゲームの終盤ですべての手を探索して、最も石を多く取れる手を求めることです。
完全読み切りでは、縦型探索のアルファベータ枝刈りというのが一般的ですが、今回は、アルファベータを行わず、単純に最大値を求めるだけにしました。
ゲームなので、勝てば良いという意味では、勝てる手を見つけた時点で終了するというのもあります。これも今回入れてません。
上に「とりあえず」って書いたように、まだ手を入れたいところはあるのですけど、まずは動作レポートってことで。
実行性能ですが、下記の一手目で7,8秒かかっている感じです(Core-M3 1.1GHz、ザクッというと12inch MAC BOOKです）。空きが９箇所なのでかなり遅いです。早くするだけなら２、３倍は軽く早くなると思いますが、所詮はこんなもんですよね。Prologだもん。
Game Playing
[teabn,white,[18,28,81,82,26,36,35,25,24,23,45,56,74,75,63,62,53,44,42,76,78,68,67,57,87,86,85,84,83,58,48,47,38],[37,46,73,34,33,21,32,31,41,51,61,64,65,52,54,43,66,16,15,14,13,55]]
1 2 3 4 5 6 7 8
1 . X X X X X . O
2 . . X O X O . O
3 X O X X O O X O
4 X O X O X X O O
5 X O O O X X O O
6 X O O X O X O O
7 . . X O O O . O
8 O O O O O O O .
[Coms move,72,-43]
こんな感じになります。白の手番で72が最善手、勝敗は-42なので大敗ですね（笑）。
ここで逆らって72ではなくたとえば77に置いたりすると、次の先手番でこういう評価になります。
[teabn,black,[18,28,81,82,26,36,35,25,24,23,45,56,63,62,53,44,42,78,68,87,86,85,84,83,58,48,38],[77,76,75,74,67,57,47,37,46,73,34,33,21,32,31,41,51,61,64,65,52,54,43,66,16,15,14,13,55]]
1 2 3 4 5 6 7 8
1 . X X X X X . O
2 . . X O X O . O
3 X O X X O O X O
4 X O X O X X X O
5 X O O O X X X O
6 X O O X O X X O
7 . . X X X X X O
8 O O O O O O O .
[Coms move,88,44]
88を取ってさらに１個多く取れるようです。
プログラムですが、読み切り用に書いた部分の概要を以下に示します。
(1)読み切り用のメイン部分
doYomikiri(Teban,Move,Eval,Black,White)
Teban:今の手番 (入力)
Move:最善手(戻り値)
Eval:評価値（石数の差分、戻り値)
Black:黒石の置き場所リスト(入力)
White:白石の置き場所リスト(入力)
・ゲーム終了時は石を数えて、勝敗を確認
・パスの時は、相手の手番で読み切りを継続
・置ける場所がある時は、先読みを実行。以下を呼び出す。
doYomikiri1(Teban,Black,White,MoveList,Move,Eval,CMove,CEval).
(2)読み切りのサブ：候補手を回して最善手を求める（１）
doYomikiri1(Teban,Black,White,MoveList,Move,Eval,CMove,CEval).
Teban:今の手番 (入力)
Black:黒石の置き場所リスト(入力)
White:白石の置き場所リスト(入力)
MoveList:石の置ける場所リスト(入力)
Move:最善手(戻り値)
Eval:評価値（石数の差分、戻り値)
CMove:今までの最善手(入力)
CEval:今までの最高評価値（石数の差分、入力)
・置く場所がなくなったら今までの最善手/評価を返します。
・置ける場所があれば、
- 石を置いて、Black , Whiteを更新(Black1,White1)
- 相手番で読み切りを行う
doYomikiri(Teban,Move,Eval,Black,White)
- 最善評価値は相手の最大値なので、符号を入れ替える
相手の勝ちは自分の負けですから。。
- 現状での最善手/評価値を更新して、MoveListの残りを試す
doYomikiri2(Teban,Black,White,Rest,Move,Eval,CMove,CEval,SEval,AMove)
(3)読み切りのサブ：最善手/評価値を入れ替えるため
doYomikiri2(Teban,Black,White,Rest,MoveList,Eval,CMove,CEval,SEval,AMove):-
Teban:今の手番 (入力)
Black:黒石の置き場所リスト(入力)
White:白石の置き場所リスト(入力)
MoveList:石の置ける場所リスト(入力)
Move:最善手(戻り値)
Eval:評価値（石数の差分、戻り値)
CMove:今までの最善手(入力)
CEval:今までの最高評価値（石数の差分、入力)
SEval:今探索した手の評価値（石数の差分、入力)
AMove:今探索した手(入力)
・今までの最高評価値(Ceval)と探索した手の評価値(SEval)を比較して、入れ替えて
doYomikiri1(Teban,Black,White,MoveList,Move,Eval,CMove,CEval)
を呼び出します。
こういうのも、 () -> ; 的な処理で書いてもいいのですけど、個人的にはこうやって分けちゃうことが多いです。なんとなくPrologでif分的な処理を内部に入れたくないという思いだけなんですけどね。あはは。
あと、ここで、SEvalが１より大きければ探索を終了するって書き方ができます。とりあえず勝つ手を返すので、処理が（かなり）早くなります。
で、アルファベータにするには、doYomikiri(Teban,Move,Eval,Black,White)でアルファ値とベータ値も入力にして引き回すことになります。ただし、述語の本体でif分書かないといけなくなりますので、今回やったように述語を分けて処理するとか、if分的構文を気分悪いけど突っ込むのか。いやはや、こういうのって苦手ですよね,Prologは。
もちろんforall的に手と評価値のペア求めて最大値探してもいいんですが（つーかProlog的には綺麗なんだと思う）、それじゃ枝刈りできないですからねぇ（笑）。
あぁ、やっぱりこういう枝刈りにはなんか向いてない気がします。
時間があったら、下のコードも少し直していきます。行き当たりばったりなので、ちょっと綺麗じゃないです。
中間評価関数は、この機構をそのまま使って、石の数数えるところで評価関数を呼べば、そのまま完成です。オセロの中間評価関数については、何十年も前からいろいろあります。
おまけだけど書いておきます。
・基本は、相手の着手数（盤上で置ける場所）を最小、自分の着手数最大になるようなところを選択していきます。
相手の選択肢を限定することは、相手が置きたくない場所（次にカドや辺を取られる）に置かせるという意味や、カドを取って辺を伸ばしていくと相手にひっくり返されない場所が増える（相手の着手数が減ります）、さらに自分の選択肢も増えていくという意味があります。
・カドの取り合いには行くつか定石的な手順があるので、そういうのを織り込んでいくこともあります。
これは、文章だと書きにくい（笑）、たとえば相手にわざとカドを取らせて、大きく取り返すみたいのがあります。
---8<------8 p="">
countBoard(black,Eval,Black,White):-
getListSize(Black,BCount),
getListSize(White,WCount),
Eval is BCount - WCount.
countBoard(white,Eval,Black,White):-
getListSize(Black,BCount),
getListSize(White,WCount),
Eval is WCount - BCount.
doYomikiri(Teban,0,Eval,Black,White):-
isGameEnd(Black,White),!,
countBoard(Teban,Eval,Black,White).
doYomikiri(black,0,Eval,Black,White):-
isPass(black,Black,White),!,
doYomikiri(white,_,WEval,Black,White),
Eval is -1 * WEval.
doYomikiri(white,0,Eval,Black,White):-
isPass(white,Black,White),!,
doYomikiri(black,_,BEval,Black,White),
Eval is -1 * BEval.
doYomikiri(Teban,Move,Eval,Black,White):-
makePutList(Teban,Black,White,MoveList),
doYomikiri1(Teban,Black,White,MoveList,Move,Eval,0,-100).
doYomikiri1(Teban,Black,White,[],Move,Eval,Move,Eval).
doYomikiri1(black,Black,White,[AMove|Rest],Move,Eval,CMove,CEval) :-
doMove(black,AMove,Black,White,Black1,White1),
doYomikiri(white,_,SEval,Black1,White1),
SEval1 is -1 * SEval,
doYomikiri2(black,Black,White,Rest,Move,Eval,CMove,CEval,SEval1,AMove).
doYomikiri1(white,Black,White,[AMove|Rest],Move,Eval,CMove,CEval) :-
doMove(white,AMove,Black,White,Black1,White1),
doYomikiri(black,_,SEval,Black1,White1),
SEval1 is -1 * SEval,
doYomikiri2(white,Black,White,Rest,Move,Eval,CMove,CEval,SEval1,AMove).
doYomikiri2(Teban,Black,White,Rest,Move,Eval,CMove,CEval,SEval,AMove):-
CEval < SEval,!,
doYomikiri1(Teban,Black,White,Rest,Move,Eval,AMove,SEval).
doYomikiri2(Teban,Black,White,Rest,Move,Eval,CMove,CEval,SEval,AMove):-
doYomikiri1(Teban,Black,White,Rest,Move,Eval,CMove,CEval).
