こんな問題を出しました。
「preemptive "hello, world"」を、出力するプログラムを書いて下さい。
提出されたプログラム同士で対戦をします。 勝つと、勝ち点 30010 点。引き分けの場合は勝ち点 10001点が入ります。 最高の勝ち点稼ぎ優勝を目指して下さい。
戦いに使うプログラムのレギュレーションは以下のとおりです:
preemptive "hello, world"
」であること。末尾に改行はあってもなくても構いません。プログラムのレギュレーション違反、プレイヤー名未設定 は、失格となります。
既に問題は締めきっていて、結果とソースコードが
特設ページ
に公開されています。
問題文を読んだだけでは若干理解し難い感じですが、
具体的な戦いの例
をご覧になればわかっていただけるのではないかと思います。
hello, world を使ったゲームを提供するというのが出題意図です。特にこのルール設定に数学的な背景やコンピュータサイエンス的な含意はありません。
ちなみに「preemptive」は「ノンプリエンプティブ な マルチタスク」の「プリエンプティブ」と同じ単語ですが、「preemptive attack」で「先制攻撃」になります。
単語の頭に「print」の最初の二文字があるので面白くなるかと思い、「preemptive」という語を選びました。
勝点の設定は、サッカーの勝点(勝つと勝点3、引分は勝点1、勝点の合計が同じなら勝ちが多いほうが上位)と実質的に同じになっています。
勝つための戦略は、大きく分けて2つあると考えています。
自分が使う文字をソースコードの先頭部分に全部並べるという作戦です。
この作戦を採用するためには少ない種類の文字数で「preemptive hello, world
」を出力できるうえに、先頭に置ける文字の自由度も大きい Brianf**k が最適となります。
防御だけだと勝てませんので、勝つための文字を頭の方に数文字配置する必要もあります。この文字の選び方で勝率が大きく変わってくるので知恵を絞る必要があります。
6位までのうち4人が Brainf**k になっていますが、いずれも この戦略をうまく実現しています。
先頭の数文字をうまく選ぶとかなり強くなりますが、鍵となる文字(Brainf**k の場合、「.」「-」「+」など)が相手コードの先頭にあると大敗しますので、対策が可能となってしまうという弱点があります。
今回は投稿済みのコードの言語が公開されるということで、Brainf**k に対する対策を入れてきた方も多かったようです。
同じ文字を二文字以上使うことを避け、その上で前の方に相手が使いそうな文字、後ろの方に相手が使わなさそうな文字を配置する作戦です。
一見ソースコードに見えないような文字列できっちりと「preemptive hello, world
」を出力できる、Bash、PHP、Perl などが向いているようです。
勝敗が文字の選び方、順序、相手との相性に依存しているので不安定な感じですし、よりよい文字の並べ方を探す手がかりが少ないので、難しいところもあります。
しかし、この作戦をとっているプレイヤーに対する対策が困難であるというメリットもあります。
優勝している Bash のコードが採用している戦略です。
戦略が2つと書きましたが、折衷案のようなものもありますので、単純に二分できるということでもありません。
勝つためには
などが要求されていたと思います。
不完全情報ゲームですし、運の要素も多分にありますが、上記のスキルを発揮できていれば上の方の順位が取れていたのではないかと思います。
それと。
10位以内に入っているコードの大半は、人間が直接書いたものではなく、人間が書いたプログラムが出力したものであるように見えます。
そういったプログラムをさらっと書く能力も、このゲームに勝つためには重要だったと思います。
今回も言語仕様と採点システムの重箱の隅を突く素晴らしい解答が集まり、運営側としても楽しめました。
一点だけ残念だったのは、レギュレーション違反による失格者が 20名以上いた事です。
ソフトウェア開発という見方をすると、レギュレーションの部分は基本的な要件に当たります。ここがしっかりおさえられていないと、仕事でのソフトウェア開発は難しくなってしまいます。
ハッシュタグ#先制hewoで Tweet された挑戦者の皆様の記事をいくつか紹介しておきます。:
いずれも大変おもしろい記事です。一読をお勧めします。
この問題を運営するにあたって、いくつかプログラムを書く必要がありました。
書いたものと、何で書いたかを(全部ではありませんが)簡単に表にまとめました:
説明 | 基盤 | |
---|---|---|
Sample Games for 先制 hello, world | haml / CoffeeScript / jquery | |
特設ページ | 投稿情報をパースする | ruby |
投稿されたコードを 実行くん で動かす | ruby /watir/ Firefox / YAML | |
コード同士を戦わせる | ruby / YAML | |
得点・順位を集計する | ruby / YAML | |
HTML の生成 | ruby / haml | |
全試合 | HTML の生成 | ruby / haml |
各試合 | HTML/JS の生成 | ruby / haml |
クライアントサイド | CoffeeScript / jquery | |
フィードバック用データの生成 | ruby |
ご覧のとおり、クライアントサイド以外は全部 ruby です。
CoffeeScript を使っているのは、JavaScript に慣れておらず、間違って
==
を書いてしまったりしそうだからです。
watirは、ブラウザをコントロールする gem です。実行くんを ruby で動かすために使いました。
YAML は、コードの実行結果や対戦結果をシリアライズするために使いました。Marshal にしなかったのは、シリアライズの結果をエディタで確認できるからです。
投稿は のべ350通を超えました。ありがとうございます。
実行せずにわかるレギュレーション違反や、集計のタイミングの関係で実行する必要のないものを除き、
252本 のソースコードを実行くんで動かしました。
コードとコードの戦いは、1万3千 回余りです。
投稿情報のパースに失敗したり、実行くんでの実行に失敗したりといろいろありましたが、最終的にはうまくまとめることができ、ほっとしています。
またこういったなんだかよくわからない問題を出したいと思っています。
なんだかよくわかる問題も出題中です。
バス代(
初級編
・
ややリアル編
) や
テトロミノ
もよろしくお願いします。