計測自動制御学会鹿北支部第175同研究集会（199乱6．19）
資料番号1T5−4

競争巡回形知能ロボット制御用先読エンジンの設計
Design of the Search Engine for CompetitiveJy Trave＝ng
JnteHigent−Robot

苫米地宣裕
Nobuhiro Tomabechi

八戸工業大学
Hachinohe lnstitute of Technology

キーワード＝競争（competition），挙回（traveling），知能（intJe11igent），ロボット如加吼先読（配arCh），エンジン（en如1e）

連絡先：〒031−8501八戸市大宇妙手人間8壬主−1八戸工業大学苫米地宣裕
rTlelO17日一25一路05l；FaxO17き弓・25−1L13n，Emai1：tOmabech＠hi−teCh．acjl）

機能を並列ハトドゥエアによって高速に実行で1．はじめにきるようなプロセッサ（先読エンジンという）の構成法を検討する。
本研究では、自分と利益の反する相手があり、先読エンジンに要求される機能i■よ、先読みとい相手と争いながら何事かを自律的に実行するよ

う点では共通性はあるが、具体的な点は対戦の内うな種類のロボット（対戦ロボットという）を対容によって異なる。本研究では、ある区域に散在象とする。対戦ロボットに特徴的な課題は、相手する目標物を自律的に移動Lながら争って収集に勝つために、相手の行動を一千測L適切な対策をするロボット（競争巡回形知能ロボットという）適択するという作業（先読みという）にある。先について検討する。対戦の内三酎■ユ、結局、ト種揖

読みには、相手の行動を読む、作戦を立てる、知ゲームとしてモデル化されることになる。また、識を生かすなど人」二知能的課題川が多く含まれ某ロボットの動作を取り扱うには、ロボットの動ているし．一般に、先読みは読みの深さが深くなる力学モデルを明らかにする必要がある巾本稿￣PFまと処理時間が飛躍的に大きくなる（2）。しかヰ）、動力学モデルは省略し、もノ」ばら、ゲ・一ムモデル

対戦ロボットにはリアルタイム応答が要求されのみを触り扱うこととする。

る。．本研究では、対戦ロボットに共通する先読み

本稿では、まず対戦のゲーームモデルを示し、次に本ゲームモデルに適した最善手探索方法としの得点に加算される。そして、目標物は削除されて、目標物に直行する動作を単位とする探索方法

るこ、を提案している。また、多数のエージェントプロ

［／レール11］2つのロボットのスタート位置は、セッサを用意し、先読みを分担して実行するとい相互に対称な最も離れた2つのマス目をとる。

う先読エンジンの構成法を捷案している。

［ルール12］ある回数の対戦を行い、合計得点差＞Hのとき先手の勝ち、そうでないときは後手2．対戦のゲームモデルと性質の勝ちとする。ただし、Hはハンデキャップの値を表わしており、多くの対戦結果に基づいて適切2．1ゲームモデルに定める。
圃1に、領域が8）〈8、目標物の数B＝6の場

本研究では、ある区域内の目標物を競争しながら収集するロボットについて検討する。このとき、合の初期局面の例を示している。図において、A区域の広さ・形状、障害物の有無、ロボットの機は先手ロボット、Bは後手ロボット、分数式n／能（進行速度、方向転換に要する時間、双方のロmは目標物を表わしている。nは目標物の番号を、ボットの機能が同じか異なるか）、目標物の価mはその価値点を表わしている。

値■分布などを明らかにする必要がある。本稿では、以下のようにゲームモデルを設定する。、

之．2 ゲームの数学的性賢［ル】ル1］区域はMXNのマス目で表わされはじめに用語を定義する。

る。

［定義1］距離：地点Pから地点Qに至る最短［ルール2］区域内に障害物はない。

経路に含まれるマスの数をPとQの距離といい、［ルール3］双方のロボットの機能は等しい。

Ip−Q‡と表す。

［ルール4］ロボットの位置、およぴ、目標物［定義2］勢力圏：「ロボットAとの距離」が「相の位置はマス目で表わされる。1個のマス日には、手との距離」より大きいマスの集合をロボットA

一時に1個のロボットだけが存在できる。の勢力圏という。2つのロボットからの距離が等［ルール5］ロボットは一つのタイミンダで、しいマス目は先手側の勢力圏に含める。

現在位置のマス目の8近傍の任意のマス目に捗

［定義3］直面目標；ロボットの現在位置からあ勤できる。

る目標物までの最短経路中に他の目標物が存在［ルール6］2つのロボットが同一のマス目にしないような目標物を直面目標という。（青いか入ろうとするとき、いずれか一方が優先権を有す

えると、他の目標物の位置を経由してその目標物る（俸尭権を有する側を先手、その反対側を後手に到達すると、直行するよりも距離が長くなるよという）。

うな位置にある日横軸を直面目標という）。

［ルール7］目標物の数Bは変数とする。

［定義4］非切迫度：ある目標物について（自分［ルール日］目標物は価値を表わす点を有する。との距離一−「・相手との距離）をその目標物の非切迫「ルール9］目偉物の分布はランダムとする（1度という。

回の対戦ごとに乱数によって決定する）。

本ゲームについて次のような性質が成り立つ。

［ルール10］ロボットが目標物の置かれたマス［定理1］ロボットをA，8、2つの目標物をⅩ，目に入るとその目標物の価値点がそのロボットYと表す。Ⅹ，YともにAの勢力圏内にあり、か2

つ、Aに対してもBに対Lても直面目標であるとトー、・、する。いま、IA−Y】＞lAXとする〔−ノ こ③ 自分の勢力圏内にある目標物の価偶の合計点のとき、次の条件が成り立っならば、BはⅩ，Yが大きな晒になるような位置にあるもの。のいずれか・方を取ることができる。

IAⅩ†lx十⊥Yl＞B−XI AND

3．2 最善若手探索アルゴリズム

IA−Ⅹ＋lx−Yl＞トB一ヽrl

本ゲームモデルでは、ロボットの動作の最小単（証明〕AがXに直行するならi■よ、BはYに直行

位は1マスの移動となるが、こ即1マス単位の探しAより先にYに到着−・PきるこAがYに直行する索を行うと、探索空間が広くなり先読みに要する

ならば、Bは1′に直行しAがYの地点に入ったと時間がかかり過ぎるので現実的￣Pない。そこで、きXに直行すれば、BはAよりも少なくともlタ

目標物へ直行する動作を単位とする探索方法を

イミング早くⅩに到着することができる検討する。まず、着手を次のように定義する。

。 □［定義5］着手：ある目標物に向かって最短距離［定理2］ロボットをA，B、2つの目標物をⅩ，Yと表す。Ⅹ，YともにAの勢力圏内にあり、か￣P直行することを着手というr一着手を目標物に直行する動作を単位とすると、つ、Bに対してYは直面目標であるがⅩは直面目標でない（HはYを経由し′てⅩに到着する）とす

着手の回数は目標物の個数Bと等しくなる。着手る。このとき、几はX，Yの両方を取ること郎での回数をBとすると悉皆探索を触った場合の探きる。

索の数ほ□！となる。．従って、Bが人きくなると（証明）AがまずYに直行し次にⅩに向かえば、悉皆探索は非現実的となる。木ゲームモデルには、AがY、Ⅹの両方にBより先に到着できるのは明将棋の詰みや連珠の5連のょうな「突然の終局」

白である〔．

「がないので、探索方法としてはα「β探針1）・（2J

定理1、定理2は、相手の勢力圏内にある目標が有効となると考えられる。ただL、上記のょう物でヰ〕、配置によっては一部を取ることができるに目標物に直行する動作を単位とすると、先手、ことを示している（、後手が常に交互に着手するとは限らない（相手の1回♂）着手に射し、その着手の到達臣甜任以内なら3．ゲームを進める指針と最善着手の探索ば何回でも連続着手できる）。また、着手の変更があり得る。」ニのように変形されたα∵−β探索を、
以下、「非交互着手α−β探索法」とよぶことと3．1ゲームを進める指針
次のような指針でゲームを進めるのが有効とする。そのアルゴリズムは以Fのようになる。ただし、α、β他による桂刈りに関する記述ほ、通考えられる。

常のα β探索と同様なので省略Lている。

l指針1］一つの直面目標を選択Lそれに向かっげルゴリズム1］非交互着手比 β探索法て最短距離で直子丁する。

（手順1）九小 、ユニ・け旨針2］目標を決める優先順位は次のようにす（手順2〕探索杜〕探さが指定された値になるか、る。

または、目標物がなくなったときは、局面評価を①双方の勢力圏の境界線付近にあるもの。

打い、かつ、探索の深さを1レベル戻しノて手順沌喧〕白分の勢力圏内にあり、かつ、評価点の高いへ、さもなければ手順3へ。
ニ与（手順3）着手の候補をリストアップする。着手ー（相手の既得点＋相手の勢力圏内にあるの対尭とする目標物は直面目標とする。ただし、

日傑物の点の合計値相手が同一目標物に対して着手しており、かつ、（2）着手の優先順位その目標物が相手の勢力圏内にある場合は着手

手順3において着手の優先順位は次のように候補としない。

決める。

（手順4）一つの着手候補（優先順位の最も高い①まず、自分の勢力圏内にある直面日掛こ対すもの）を選択し着手する。

る着手で（価値X（P−非切迫度））の大きい目標に到着するまでの距陣をカウントする。自分ものを優先する。ただし、Pの価は経験に基づいの着手の距離が相手の着手の距離を超えたときて定める。

は手順5へ、さもなければ手番を交代せずに、探②次に、相手の勢力圏内にある直面目模に対す索の深さを1レベル深くして手順2へ。

る着手で（価値X（P＋非切迫度））の大きいも相手が同…目標軌こ対して着手しており、かつ、のを優先する。
なお、探索は着手単位で行うが、ロボットの移その日梼物が自分の勢力圏内にある場合は、相手の着手を修正させる。すなわち、自分が目標物に動はあくまで1マス単位で行う。従って、1マネ到着した時間に相手が進行した位置で停止する

移動するたびに移動した位置を基準に探索をしという着手に修正させる。

直すこととなる。
t

園2に、囲1の局面に対応する先読み探索のゲ（手順5）手番を交代し、探索の探さを1レベル深くして手順2へ。

←ムの木を示している。ただし、一部のみを示し（手順6）着手を戻す。ている。図において、0は先手のノード（着手）

先手番ならMく局面評価値、後手番ならrMく局を、ロは後手のノードを表わしている。ロロと面評価値のとき、M←局面評価値、かつ、最善着

同じ記号が連続するのは、□側の連続着手を示し手候補←着手。ている。ノードの中の分数式は、分子で目標物の（手順7）未探索の着手候補があれば手順4へ、番号を、分母で得点を表わしている。5 ／0は、さもなければ手順8√㌔5番の目標物に向かって着手したが柏手の方が（手順8）根局面ならば終了、さもなければ探索先に到着したので中途で進路を変更したことをの探さを1レベル戻して手順5へ。

表わしている。

□（1）局面評価

4．先読エンジンの基本構成

手順1における局面評価は先読みの性能に大きな影響を与える。本ゲームモデルでは、局面評価に寄与するファクタとして次が考えられる。①

非交互着手α−β探索アルゴリズムにおいて、■ 自己の既得点、②相手の既得点、③自分がこれか処理時間は、主として次によって決定される。①

ら得点できる可能性、④相手がこれから得点でき着手候補リストアップと優先順位決定に要するる可能性。

時間、②局面評価時間、③探索のくり返し回数。

本稿では、局面評価を次式のように行う。

従って、先読みの処理速度を向上させるためには、局面評価値＝自己の既得点＋次のような方策が有効となると考えられる。①着
手候補リストアップ、着手候補の優先順位決定、自己の勢力圏内にある目標物の点の合計値
4およぴ、局面評価をハードウエアによ′」て行う、・こ訪主プロセッサi■ま、す′ミての着手候補について②前項のハードウエアから構成される部分探索の評価値が得られたら、最善着手を決定する。

ハードウエアを多数用意L■全体の探索を並列に5．むすぴ実行する。ただし、全体の探索を並列に分割する
方法としては、枝刈りがあるため、先頭の着手ごとに分割し ーつの着手は独立のハードウエアで

本稿では、ある区域に散在すろ目標物を白律的処理しさらなる分割はしないとするのが有効とに移動Lながら争って収集するロボット（戯争巡なる。

回形知能ロボット）を取り上げ、対戦［■∫ポットに

本稿では、以7￣のような先読エンジンの構成法

共通する先読み機能を並列ハードウエア・によノjて高速に実行できるプロセッサ（先読エンジン）を提案する。
先読エンジンを、ある深さの探索を独立に実行の構成法を検討した〔一 まず、対職のゲームモデルするエージェントプロセッサ（APと）1う）複数を設定した。次に、木ゲームモデルに適した最善と各APに探索局面を割り当てる圭プ【1セッサ

手探索方法として、目標物に直行する動作を単位で構成するL本構成を図3に示している。とする探索方法俳交互着手α−β探索法）を提案した。また、番数頂エージ．工ントプrJセッサに1個のAPは、探索制御回路、フィールド回路、およぴ、局面評価回路から構成される。探索制御

上って先読みを分担して実行する先読エンジン
竃回路は、①フィールド回路、優先度計算回路、の基本的な構成法を提案Lたし＝

局面評価回路の制御、②最善手の決定即機能を今後、次郎ような課題について検討する了・定で有する。フィールド回路はゲームの行われる区域ある。に対応づけて構成され、卓〕ロボットの移動、②〔臼シミュレーションソフトウエアを作成L、非R標物の消去、回復、③直面目標の検出の各機

交互着手α β探索蛙♂沌￣効性を検証する．．

能を有する。．AIJ〔7〕構成を凶4にホLている。

②エージニ〔ントプ1Jセッサと先読エンジン全体の詳細な論理設計を行う。

主プロセッサは次の機能を有する．1
仕初期設定、②局面の表示、④ゲーームの進行、③先読エンジンを集積したVLSlチップの設④APU）機能、⑤各APへの探索局面の分配計・製作を行う。

本先読エンジンは次のように動作する。

①圭プロセッサは、1〜2手先までの可能な若参考文献

干候補をすべて求める。

②主プロセッサは、各APに着手候補を割り当（1）人工知能学会編：人二L知能ハンドブック、てて探索を命令する。

オし一ム引二（1990）．
（2〕小谷、吉川他：コンビュし一夕将棋、③・各APは、与えられた着手候補について指定きれた探さまで探索する．1探索を終えたAPは主サイエンス仕〔199印．

プlコセッサに指定された若草の評価値を知らせる。
④幸プロセッサは空いたAPが生ずれば、別な着手候補を㌧一えて探索を命ずる。
5A：先手ロボット、B：後手ロボット、。／m＝ 目標物の番号／価値点
図1ゲームの翫親局面の刷

一望点
局面評価点

○：先手ノード［コ：後手ノードn／m：目標の番号／簡点

国宝ゲームの木偶1の局面に対応）

図3先読エンジンの基本構成

tフィールド回路

B

3／
探索

2／6／

制御

局面評価回路

回路

4／
5／1

1／2
A

着手リストアップ

囲4エージェントプロセッサの構成

7