五目並べの実装 B4 グェン トアン ドゥク 内容 1. 目的 2. 五目並べのルール 3. ThreatとThreat sequence 4. 戦略 5. 探索アルゴリズム 6. 評価関数 - Threat space search(Threat空間検索) 7. 結果 1. 目標 今回の目標 • 五目並べプレイヤーを作る • 評価関数とalpha-beta法を使う • 特に五目並べのための探索技術である threat space search(threat空間探索)を実装 する • 先に打つなら勝つ、そうでなければ、よく守 れるプレイヤーを目指す 2.五目並べのルール 五目並べのルール • 15x15ボード上でBLACKとWHITEが升目 に自分の色のマークを置く • BLACKは先に行く • 先に5つ連続な目を作れたら勝つ • ボードがいっぱいになっても勝つ人がいな ければ、引き分ける 連珠のルール • 五目並べと似ているが、ボードのサイズは 19x19 • 先に打つ方(BLACK)にはたくさん制限が ある(Overlineしてはならないなど) • ボードのサイズが大きければ大きいほど 先に打つ手(BLACK)は利益があるからで ある。 今回実装している五目 • ルールは五目並べのルールと同じ • しかし、ボードのサイズが19x19 3. ThreatとThreat sequence Threat • Threat: -相手がすぐ対応しなければならない列 -例: BLACKのマークが3つ連続した列 (WHITEが対応しないと2手後負ける) Threat の種類 • • • • • Threatはそれぞれに名前がついている 3つ連続した目: three 3つ連続しない目: break three 4つ連続した目: four 5つ連続した目: five Threatの例 Threat sequence • Threatを連続的に生成する -第一のthreatに相手が対応しなければな らないので、引き続いて自分がその次の 手でthreatを生成する -相手はどう対応するかにはまず考えない。 自分が勝手に打てると仮定する。 Winning Threat sequence • 勝つまで連続したthreat sequence • 例: G H I J K L M 13 12 O O X O X O 11 O X X X X 10 X O X O 9 8 Xのsequence: J11, J9, J10, M10/J8/J12 Potential Winning Threat Sequence • Winning threat sequenceになる可能なthreat sequenceはPotential Winning threat sequence(PWTS)と呼ぶ • そのsequenceに対応するうちに、相手はWinning threat sequenceを生成する場合があるので、 PWTSはいつもWTSになるとは限らない • PWTSには、相手はどう対応するかを考えないか らである。 WTSにならないPWTSの例 I12, (I9), H12, (F12), H15 (X: I12, H12, H15) E F G H I 15 14 X O 13 X 12 X O X X X O O X 11 O X 10 O O 9 4. 戦略 人間の戦略 1. ボードのある部分を見て、Winning threat sequence(WTS)を探す 2.まず、自分の打った手と次の自分の手だ け見る。相手はどう対応するかはまず考え ない 3. もし、WTSが見つけたら、相手がどう対応 するかを考える コンピュータの戦略 • 状態空間探索 5. 探索アルゴリズム 状態空間探索 • 手を生成しながら、新しい状態を作る -最後まで(10手先)の状態を全部見えない 調べる状態数が大きい過ぎる - 適当な評価関数で、数手先見る • 同じ状態が違う手の順番であり得る(木で はなく、グラフ)ので、transposition tableを使 う • α-β枝刈りで効率を上げる. Threat空間探索 • 評価値を決めるために、threat空間探索を する。 • それにより、winning threat sequenceが見つ かれる。 6.評価関数 評価関数の重要性 • 完全にゲームの最後まで先に見えないの で、評価関数で手を選択しなければならな い。 • 評価関数が良ければ良いほど、強い。 • 評価関数が悪ければ、容易に負ける。 五目並べでの評価関数 • • • Threat空間探索 局面にもとづく評価値 評価値は、 - Threat空間探索によって決める - Threat空間探索によって決められない 場合は局面の列の形により決める Threat空間探索 • WTS(winning threat sequence)はthreatsを 含んでいる • そこで、全てのthreatsの空間に注目する。 Threat space(threat空間)と呼ぶ • Threat空間での探索をすると、WTSが見つ けられる。 • Threatの数はあまり多くないので、調べる 状態はあまり多くない。コストが小さい。 Threatの要素の定義 • Gain square: threatの中の攻める人の打つ 位置(square) • Cost square: threatの中の守る人の打つ位 置 • Rest square: threatを作る可能のある位置 (gain squareを除く) 例 Threatの従属性 • Threat A がthreat Bに従属される(A is dependent on B)とは、Aのあるrest square がBのgain squareである。 • Threatの従属木(dependency tree): - ノードがthreat - rootノード以外のノードは全て、親ノードに threat従属される 衝突する従属木 • 従属木PとQが衝突するとは、 Pにあるthreat AとQのあるthreat Bの間で、 - Aのgain squareがBのcost square または、 - Bのgain squareがAのcost square または、 - Aのcost squareがBのcost square である • 例 衝突するThreatの性質 • 2つの衝突するthreatは同時に実現できな い。 • つまり、dependency treeには、2つの衝突す るthreatは存在しない。 • 探索するときに、これを利用するとノード数 を減らすことができる。 • しかし、従属するthreatを見つけるために、 コストがかかる。 衝突するThreatの例 • E15とD15が衝突している Threat空間探索の規則 • Threat Aがthreat Bに独立(従属ではない) であれば、AはBの探索木に現れない。 • Threat空間探索木には、threatをgain squareと方向、種類で表現する。 • その探索木には、攻める人の手だけ現れ る(調べるノード数が減る)。PWTSが見つ かったら、それがWTSかどうかをチェックす る Threat空間探索の例 Depth Threat type Gain square Cost square 1 Four D15 E15 1 Four E15 D15 Four I11 H12 2 3 2 1 2 2 3 Straigh four I8 I7 Four H12 I11 Three I11 I7, I8, I12 Four H12 E15 Four E15 H12 Five D15 Threatの発見 • 打つたびにthreatが生成するかどうかを見る • 生成したら、新しいthreatを作り、threat listに保存 • 既に存在するthreatのtypeが打つ手により変わる ことがあるので。変わったthreatをthreat listに追 加 • それ以外(自分の)threatはそのままthreat list に 追加 • 相手のthreatはその打った手によって、killされる かどうかをチェック PWTSの探索 Threat-sequence-list sq = empty; Pwts-search( board, threat, sequence ) { if( wts-found ) return; if( threat.type == FIVE ){sq.add( sequence ); return;} for each Position in threat.gain_squares { do_move(board, Position); sequence.add( Position ); Pwts-search( board, threat.child, sequence ); restore_board(); sequence.remove( Position ); } } 評価関数 Int evaluate(board, man-threat-list, machine-threat-list, turn){ If( turn == machine ){ for each threat in machine-threat-list{ sq = Pwts-search( board, threat ); if( sq is WTS ) { return INFINITY; } } } else { //find WTS for man if( sq is WTS ) return MINUS_INFINITY; } return evaluate-board-state( board, man-threat-list, machine-threat-list, turn ); } 7. 結果 実験結果 • 五目並べプレイヤーを作った。 • Threat space searchを行ったが、threatを発 見するのがあまりよくなくて、全てのthreatsequenceを見つけなかった。 • 時々、明らかに勝つ手があるのに打ったな い(そのthreatが発見できないため)
© Copyright 2024 ExpyDoc