ぴたすちお、一人麻雀練習機などの自作フリーソフトの配布、数独などのパズル、麻雀、その他もろもろ
あらのHP 数独まにあ エクセルまにあ 麻雀研究所 賢く儲ける株式投資 お釣り ダイエット なたでぽぽ FX



スポンサードリンク


ロボコードについて

ロボコード(Robocode)とはIBMで開発された戦車ゲームです。
Javaで戦車のようなロボットの動きをプログラムし、他のロボットと対戦させます。
ロボコードの本体は こちら からダウンロードすることが出来ます。

世界中で大会が行われており、日本でもIBMの主催で
Robocodeジャパンカップが2002年12月に行われました。
私はSheraというロボットで参加し、運良く優勝することが出来ました。
ここではその経験を活かして、強いロボットを作るためのポイントなどを書いてみたいと思います。

ロボットの強さを決める要因はいろいろありますが、おおまかに言って

に分けて考えることが出来ると思います。
これらについて一通り触れた後で、細かな事や感想などを述べます。

スポンサードリンク

戦略

まず、強いロボットとは何か、を考える必要があります。

単純に相手を倒せば良いというわけではありません。
それはロボコードがスコアをもとに勝敗を決めるためです。
スコアは生き残りによる点数と相手に与えたダメージによる点数の合計で計算されますが、
一般的にこの2つは相反するものです。
攻撃的なロボットは相手に多くのダメージを与えることが出来ますが、勝率は悪くなります。
逆に守備的なロボットは攻撃にエネルギーを使わないため、生き残る確率が高くなります。

このバランスを考えて、どの程度攻撃的なロボットにするかを決める必要があります。
これは、参加する大会のルールによって変わってきます。
例えば、 face2face という大会では、
ロボットは1on1でトーナメントを行います。
各対戦では単純にスコアによって勝敗が決まるため、相手よりも多くのスコアを得る事が目的となります。

しかし、 Robocode RumbleRobocode ジャパン・カップ では微妙に事情が違ってきます。
これらの予選ではトーナメントではなく、リーグ戦によって順位が決まりました。
目的はスコアの合計を最大化すること、になります。
必ずしも各対戦で相手よりも多くのスコアを出す必要はないということです。
そのためトーナメントに比べて、攻撃的なロボットが有利になります。

逆に Survivalist League では純粋に勝率によって順位を決めるため、
生き残り率を重視したロボットが上位にランクされます。

また、 Eternal Rumble では独自のレーティングを計算しているため、
それに対応した攻撃性を考える必要があります。

Meleeでは話はもっとややこしくなります。

などが考えられます。
どのような戦略が良いかは、対戦相手の戦略や、置かれている状況によって変わってきます。


スポンサードリンク

レーダーの動かし方

1on1では何も考えることはありません。
相手は一人なので、常にその相手を監視するだけです。
これによって、相手の動きや弾を撃ったタイミングを全て把握でき、 それを基にして将来の予測が出来ます。

問題はMeleeの場合です。

などが考えられます。

ロボットがいる範囲だけを往復させるのと単純にクルクル回すのを比較すると、
前者が優れているようにも思いますが、そうでもありません。
自分が壁沿いにいれば180度、隅にいれば90度のスキャンで良いのですが、
真ん中にいるときには結局360度近くの範囲を見る必要があります。
このときレーダーの回転方向を変えた直後に見つけた敵は
その後300度以上回して、方向を変え、300度以上戻ってきた後に再び視界に入ります。
単純にクルクル回していれば360度ちょっと回す間にすべての敵を見ることが出来るので
自分が真ん中にいるときにはその方が良いことが多いです。

狙っている敵を追いかける方法は有力です。
敵の動きの予測アルゴリズムにも依存しますが、一般に長期間監視しているほど
正確な予測が出来ると考えられます。
しかし、あまりその敵に注目していると背後から近付いて来た敵に気が付きません。

従って、基本的には狙っている敵を追いかけていて、一定時間ごとにクルッと回す、
というのが良いと思います。

移動

移動の目的は2つ、相手の弾を避ける事と、攻撃性を調整するために相手との距離を調整する事です。
代表的な方法としては次のようなものが知られています。

相手が弾を撃ったらちょっと動く

相手の標的アルゴリズムによっては非常に有効な手法です
止まっている敵に対してその位置にしか弾を撃たない相手なら100%避ける事ができます
しかし同時に非常に予測されやすい動きでもあります
2,3発続けて当てられたら別の動きに変えるべきでしょう

相手との距離を一定に保つ

攻撃性の調整に重点を置いた方法です
相手を中心にして円運動をし、たまに方向を変えます
あまり律儀に距離を一定にしていると、相手が突撃してきた時や、一目散に逃げた時に
動きが単調になってしまうので、適当な遊びが必要でしょう
方向転換のタイミングがランダムならそれほど動きを読まれることもないはずです

相手の動きを真似する

相手との位置関係が線対称や点対称になるように動く方法です
実装するのはとても簡単で、相手によっては結構な効果があります
相手よりワンテンポ動きが遅れてしまいますが、それが不利なのかは不明です
欠点としては、相手に勘付かれた場合には自分の動きを制御されてしまうことです

独特のパターン

TronのカクカクやPrairieWolfのクネクネなどがあります
また、Meleeでは多くのロボットが隅で決まった動きをします
動きを予測されるリスクはありますが、相手の照準アルゴリズムによってはかなりの効果がある場合もあります
あまりに単純なパターンでは当然相手に読まれるので、
適当にランダムな動きを入れるとか、複数のパターンを切り替えるなどの工夫が必要です

ランダム

適当に動く方法です
動きを予測されないという利点があり、意外と効果的です

これらの組み合わせ

実際は状況に応じて動きを変えることになると思います
例えば、被弾状況を記録して、一定以上になったら別の動きにしたりします
メリハリのある切り替えでないと効果がありません

弾の強さ

弾を撃つ時に決めることは、弾の強さとその方向です。

弾の強さは攻撃性の調整に関係します。
強い弾ばかり撃っていれば攻撃的なロボットになります。
しかし、相手との距離が遠すぎる場合には、当る確率が低いので勿体無い感じです。

そこで弾のパワーを決めるための目安として、期待値を用いる事が出来ます。
距離ごとに弾の当る確率を推定しておいて、それを基に期待値を計算します。
そしてそれがプラスの時は最大パワーの弾を撃ち、
マイナスの場合は最小パワーの弾を撃つかあるいは弾を撃たないようにします。

期待値としては、弾を撃った場合の自分と相手のエネルギー差の変化量を使います。
弾の当る確率をPとすると Power <= 1 の場合、自分のエネルギーの増加量は

- Power + 3 * Power * P

相手のエネルギーの減少量は、

4 * Power * P

になります。従って、

- Power + 3 * Power * P + 4 * Power * P > 0

を解いて、

P > 1/7

がひとつの目安になります。同様に Power > 1 の時は、

P > Power / ( 9 * Power - 2 )

であれば相手のほうが自分よりエネルギーが減ることが期待できます。

ただし、ここでは生き残りによるスコアを考慮していないので
両方が瀕死の場合は注意が必要です。
また、弾の当る確率はあくまで推定値なので、その精度には限度があります。

メモ

照準アルゴリズム

SandboxLump/DTの作者による Guess Factor Aiming が現在最も優れた方法だと思います。
Sheraも基本的にはこの手法を用いています。

また、 Mogbotの作者のページ にはパターンマッチングについての説明があります。

この2つを組み合わせるのが現状では最適だと思います。

現在Sheraでは単純なパターンのみを検出しています。
例えばMeleeで一定期間以上一歩も動かないロボットを見つけたら、
そこに向けて弾を発射します。
また一定以上直線運動をしている敵はそのまま直線運動をするものと仮定します。
同様に、くるくる検出、くねくね検出といったことをやっています。

その他

とどめの突撃

相手のエネルギーが非常に少ない場合、弾でとどめを刺さずに突撃して倒します
これによってRam damageとRam damage bonusが貰えるため、ほんの少し得することがあります
ただし不用意に近付くと撃たれることもあり損得は微妙です

とどめの一発

とどめを弾で行う場合、必要なエネルギーを計算すると節約できます
またそれだけ速い弾が撃てるので当たる確率が上がります
さらにとどめの突撃を期待して、ほんの少しエネルギーが残るように撃つのも効果的かもしれません

ファイル

Robocodeでは対戦相手について得た情報をファイルに保存しておくことが出来ます
おそらくこれは効果がありますが、Sheraではこの機能は実装していません
理由はただ単に面倒だったからです

Dual CPUマシンでのバグ

Robocodeをマルチプロセッサのマシンで動かすと、かなりの確率でフリーズします
これはRobocodeの作者も確認済みの現象ですが、 環境がないため直せないとのことです
私はVMwareでWindowsの上にWindowsをインストールして使っていました

Robocodeの今後

IBM主催のジャパンカップは終わってしまいましたが、海外ではいろいろな大会が継続中です
ロボコード関係のリンク のページでいくつか紹介しています
また日本でも有志の人たちが メーリングリスト で新大会を企画中です
また作者は Robocode2を開発中 とのことです

感想など
Java言語について

私はRobocodeに取り組むまではJava言語を使ったことがありませんでした
ロボットを作るための最初の作業はJDKのインストールだった訳です
普段はC/C++でプログラムすることが多いのですが、Javaの習得は非常に簡単でした
C++と似ているからと言ってしまえばそれだけですが、
ロボットを作るという目標があったことがモチベーション維持に繋がったことも事実です
そういった意味ではJava入門の一環としてロボット作りに取り組むのは効果的だと思います
すでにいくつかの専門学校や大学では授業でロボコードを扱っているようです
私の大学でも卒業研究のテーマとしてロボコードを扱っている方がいました

英語

強いロボットを作るためにはコツコツとアルゴリズムを改良していくことが必要です
しかし、その前にすでに作られているロボットについて調べることで大幅な労力削減が可能です
Robocodeは英語圏で開発されたため、当然それらの情報の多くは英語で書かれています
私は一応英語を読むことは出来るのですが、意外とこれが重要だったのではないかと思います
ロボコードをインストールしてJavaを覚えた後に1週間以上の期間をSurveyに費やしました

特にIBMのalphaWorksの 掲示板 は有益でした
読んでない方は是非一通り目を通して見て下さい

ジャパンカップについて

運営上の問題が多少ありましたが、ジャパンカップへの参加はとても楽しく有益なものでした
無料で数ヶ月遊ばせてもらって、Java言語も覚えることができ、
さらに賞品としてThinkPadとZaurusを頂きました
このような大会を開催してくれたIBMの方々に感謝します
是非継続してこのような大会を行って下さい

テラリウムとの比較

テラリウム とはマイクロソフトで開発された".NETによるネットワーク対戦型ゲーム"です
植物、草食動物、肉食動物の動きをプログラムし、その強さを競います
草食動物は植物を、肉食動物は草食動物と肉食動物を食料にし、成長、繁殖します

2002年5,6月に日本大会が行われ、私はlie005という草食動物で優勝しました
言語は.NETが使えれば何でも良かったのですが、C#を選びました
Javaと同じくC#もはじめての言語でしたが、比較的容易に習得することができました

無料で数ヶ月遊ばせてもらって、C#言語も覚えることができ、
さらに賞品としてXBoxを頂きました
このような大会を開催してくれたマイクロソフトの方々に感謝します

ロボコードも面白いですが、テラリウムも同じぐらい面白いゲームです
残念ながら日本では現在廃れてしまっているようですが、
アメリカでは細々とではありますが続いているようです
興味のある方は TerrariumのHP をチェックしてみて下さい

動物をいくつかプログラムしただけなのでまだ良く分かりませんが、
言語としては後発の分だけC#の方が洗練されている印象があります
現在はC++を主に使っていますが、JavaかC#を選ぶような時が来たらおそらくC#を使います




このページに対するご意見ご感想は (ara999 あっと gmail.com ) までお願いします

あらのHP 数独まにあ エクセルまにあ 麻雀研究所 賢く儲ける株式投資 お釣り ダイエット なたでぽぽ FX