【逐次環境部門全体講評】
今年度の逐次環境部門の課題であるひとりポーカーは, 広い探索空間を持つ組
合せ最適化問題である。すべての場合をシラミ潰しに調べることは事実上不可
能なので, 高いスコアを得るためにはなんらかの近似的手法が必要である。昨
年度に比べて問題が難しかったためか, 応募作品数は8件と数少なく, 正常に
動作したものは7件であった。応募作品にはさまざまな工夫が見られ, 昨年度
に比べて平均水準はかなり高く, 審査する側も大いに楽しめた。
応募プログラムは以下の手法のいずれか, またはそれらの組合せを用いたもの
であった。
- 高得点の役を見つけるヒューリスティクス
- ヒューリスティクスで限定した探索空間内の全探索
- 山登り法による改善
- シミュレーティドアニーリング法による改善
審査は意図的に高得点を出しやすく構成したカードの組合せや, 乱数で生成し
たカードのいくつかの組合せについて, 各作品が時間経過とともにどのように
解を改善されていくかをみる方法をとった。早めに高いスコアを出すもの, 出
足は悪いがジリジリとスコアを伸ばしていくものなど, 用いたアルゴリズムに
よって作品ごとの特性はさまざまであった。最終的には, ある程度のスコアに
達するまでの時間と最終的に到達したスコアの両面を勘案して, 入賞作品を決
定した。
《最優秀賞》横山 大作 殿（東京大学 電子工学部 電子情報工学科）
最優秀賞に輝いた作品のアルゴリズムは, ヒューリスティクスに基づく初期状
態から2カードの交換を基本操作としたシミュレーティド・アニーリングを行
なうものである。初期温度は 30,000点, 冷却率は100回の交換ごとに 0.95 と
している。温度が100点を下回るとふたたび 30,000点に上げて探索する。
この作品は計測したどのカードセットについても安定してよいスコアを残した。
低得点しか得られないセットについては, 当初はあまりよい点が出ないが, じ
わじわとスコアを伸ばし, いずれも結局時間内に応募作品中で最高のスコアを
出している。かなり高得点が可能なセットについては早めにかなり高いスコア
を出しているが, 最終的には最高得点には至らなかった。
初期値を決めるヒューリスティクスは, 高得点の役は見つけるが低得点の役は
見つけられないのが, 低得点セットの早期のスコアが低い原因であろう。アニー
リングによる改善は, いずれの場合もまずまずうまく働いているように見える
が, 最後の詰めが甘いのは再探索に入る温度100点が高過ぎるからではないか
と思われる。しかし, どうしても偶然性の高くなる一回のアニーリングに頼ら
ず, 複数回のアニーリングを行なっていることが, スコアの安定に結び付いた
のであろう。
アニーリングに用いた定数の決め方を工夫すれば, さらに改善する余地もあり
そうだ。たとえば, どこまで温度が下がってきた時に再試行するかの閾値を固
定せず, 試行の繰り返しとともに徐々に下げていく方法などもありそうだ。
《優秀賞》栗田 英明 殿（東京工業高等専門学校）
優秀賞を得た作品のアルゴリズムは山登り法である。単純なヒューリスティク
スにしたがった初期状態から始めて, 2カードの交換についての山登り方式の
探索を行なう。どれを交換候補とするかはランダムに決める。この作品を特徴
づけているのは, 異なる初期状態からの山登り探索を10組独立に並行に行なう
ことにある。その中で最高のスコアになったものを全体のスコアとして採用し
て出力している。それまでの最高得点との差が大きく (100,000点以上; プロ
グラム中に定数として記述) 開いてしまった探索については, それ以上の探索
をあきらめ, その時点で最高点を得ている状態を初期値にして出発し直す。初
期値の設定は, ストレートフラッシュをみつけやすいようにというヒューリス
ティクスに従っており, 10という数はこのヒューリスティクスから決まってい
る。
この作品は最初にある程度のスコアを出すまでに他の優秀な作品よりもかなり
時間がかかる傾向がある。これは初期状態を作るヒューリスティクスが不十分
(ストレートフラッシュ以外は考慮していない) であること, 10通りの山登り
を並行に行なうことによる計算量の多さなどによると思われる。しかし, 低得
点しか得られないカードセットについては, 計測した時間内に応募作品中最高
のスコアを出している。高得点が出るセットについても, まずまずのスコアを
出す。これは山登り探索を複数並行して行なうことによって, 探索が極値に捕
らわれる確率を減らしたのが功を奏したものと思われる。並列処理に拡張しや
すいアルゴリズムである点も評価できる。
初期状態を決めるのにもう少しヒューリスティクスを使えば, スコアの立ち上
がりが大きく改善できよう。山登りの並列実行数についても, 初期状態につい
ての特定のヒューリスティクスに依存するのではなく, チューニングすること
が可能だろう。
《佳作》
それぞれ一長一短のある３作品を佳作とした。
［佳作１］鶴岡 慶雅 殿（東京大学大学院 工学系研究科 電子情報工学専攻）
佳作１の作品のアルゴリズムは, ヒューリスティクスによって決めた初期状態
から, カードの交換二組 (4枚のカードを動かす) を基本操作とした山登り探
索を行なうものである。一組目の交換であまりにも (22,000点以上) 点数が下
がるようなら二組目を試さないが, 他はすべての二組交換の可能性を試して最
良のものを使っている。
この作品は初期状態設定のヒューリスティクスが優れているようで, 早めにか
なり高いスコアを出す。短時間内だけでの優劣を考えれば優秀賞の候補にもなっ
ただろう。しかしながら, シミュレーティド・アニーリングなどの手法に比べ
ると単純な山登りは極値につかまりやすいものと見えて, 時間をかけるとその
後のスコア改善が遅く, 他の作品に大きく水を開けられることがある。それで
も, 交換を二組を基本操作とした山登りとしたため, 二枚のカードの交換だけ
を考える山登り探索に比べると極値につかまる可能性を大きく減らしているよ
うである。
［佳作２］河野 洋一 殿（一般）
佳作２のアルゴリズムは, ランダムな初期状態から二枚のカードの交換を基本
操作としたシミュレーティド・アニーリングを行なうものである。初期温度は
3,000点, 冷却率は0.85とプログラム中に固定しているが, これを決めるため
に多くの実験をしたらしく, そのデータが付属文書にかなり詳しく述べられて
いた。
この作品は初期状態をまったくヒューリスティクスを使わずにランダムに決め
ているので, ある程度高いスコアに到達するまでに他の優秀作品よりかなり時
間がかかるのが欠点である。アニーリングは有効に働いているようで, 計測時
間内の最終的なスコアについては, ほとんどの例題で最優秀賞作品にもあまり
劣らないスコアを上げている。
［佳作３］檜田 和浩 殿（京都大学 工学部電子工学科）
佳作３のアルゴリズムは, ヒューリスティクスによって高得点の役を行ごとに
あらかじめ確定し, 行を崩さない範囲で列内の交換についての全探索を行なう
というものである。ヒューリスティクスで狭めた探索空間の中ですべての場合
を尽くす探索になっている。
最初に行を固定するために用いたヒューリスティクスはかなり優れたものであ
るらしく, 比較的良いスコアを出すまでに時間がかからないので, ごく短時間
(1秒程度) 以内に出せるスコアに限ればかなり優秀である。しかしながら, 完
全にヒューリスティクスに頼って探索範囲を限定してしまうので, 時間をかけ
ると他の優秀作品に追い抜かれてしまう。課題は時間制限を設けていないのだ
から, このアルゴリズムでの探索を終了した後にもなんらかのスコア改善手法
を用いた改善をはかるようにすべきだった。
逐次環境部門 全体講評