機械学習周りのプログラミング中心。 イベント情報
ポケモンバトルAI本電子書籍通販中

【CodinGameオセロ】1文字に1.994バイトを埋め込むbase63483/base63481を開発した

オセロAI

CodinGameにおけるオセロAIの対戦は、提出するものが実行バイナリではなく、プログラムのソースコードです。提出可能なソースコードは1ファイルのみで、サイズ制限は10万文字です。なお、重要なのは、サイズ制限が10万バイトではなく、10万「文字」であるということです。以前の検証によれば、UTF-16で2バイトで表せる範囲の日本語文字は1文字として数えられることがわかっています。これを利用して、バイナリデータをできるだけ多く10万文字に詰め込むことに挑戦します。

要件

  • バイナリデータを文字列定数に埋め込んだソースコードを生成します。今回は実行可能ファイル（Windowsでいうexe）を使用しますが、バイナリデータの中身は任意です。
  • 生成されたソースコードには、文字列定数を解釈して元のバイナリデータを復元するコード（デコーダ）を含めます。ただし、デコーダ自体も文字数制限のうちなので、短く書く必要があります。
  • 生成されたソースコードは、Windows上のVSCodeからChromeにコピーアンドペーストし、提出できる形である必要があります。以下で検証するように、ヌル文字が入っていると貼り付けに失敗することがあるので注意が必要です。

完成品のイメージ

状況をより分かりやすくするため、完成したもののイメージを先に示します。わかりやすさのためデコーダ部のコードは普通の書き方をしていますが、実際には変数名を1文字にするなど短く記述することがより望ましいです。

# coding:utf8
s="닄폈猼蜺..." # ここにバイナリが埋め込まれている
l=95520 # 復元後のバイナリの長さ
import lzma
import base64
import subprocess
import os

# デコーダ部
CHARSET_SIZE = 63481
UNIT_CHARS = 174
UNIT_BYTES = 347
OFFSET_TABLE = {9: 1, 12: 2, 33: 3, 91: 4, 8231: 5, 55295: 7, 65536: 2055}

def decode_chunk(chunk_text):
    bigint = 0
    chunk_binary = bytearray(UNIT_BYTES)
    assert len(chunk_binary) == UNIT_BYTES
    for i in range(UNIT_CHARS):
        c = ord(chunk_text[i])
        for upper_bound, offset in OFFSET_TABLE.items():
            if c <= upper_bound:
                c -= offset
                break
        bigint = bigint * CHARSET_SIZE + c
    for i in range(UNIT_BYTES):
        char_idx = bigint % 256
        bigint = bigint // 256
        chunk_binary[i] = char_idx
    return bytes(chunk_binary)


def decode_all(src_text):
    assert len(src_text) % UNIT_CHARS == 0
    dst_binary = b""
    for i in range(len(src_text) // UNIT_CHARS):
        dst_binary += decode_chunk(src_text[i*UNIT_CHARS:(i+1)*UNIT_CHARS])
    return dst_binary

# デコード
open('x','wb').write(lzma.decompress(decode_all(s)[:l]))
# デコードしたバイナリを実行
os.chmod('x',511)
subprocess.run('./x')

もっとも単純な方法

バイナリデータにはヌル文字(0x00)や改行(0x0A)などが含まれているため、そのまま文字列定数に埋め込むことはできません。そのため、プログラミング言語の文字列定数にはエスケープシーケンスが用意されており、\0でヌル文字、\nで改行文字相当のバイナリを埋め込むことができます。また、値がアルファベットなどに該当する場合は(例: 0x61はA)そのまま埋め込むことができます。ただし、エスケープシーケンスを用いてバイナリデータを埋め込む場合、1バイトの表現に複数文字を消費することになります。例えば、0x00を表現するのに\0を使用すると2文字必要になります。エスケープシーケンスを用いる方法は単純ですが、効率が良いとは言えません。なお、エスケープシーケンスはプログラミング言語によって異なる場合があるため、本記事ではPythonに準拠します。

base64

バイナリデータをアルファベット等の通常の文字だけで表現する手段として、base64が有名です。base64では、3バイト（24ビット）のバイナリデータを、4文字の文字列で表現します。使われる文字はアルファベット52種類、数字10種類と+/を合わせた64種類の文字（末尾のパディングに=も用います）で、1文字あたり6ビットの情報量を表現します。4バイト以上のデータは、3バイトずつ区切ってそれぞれ4文字で表現します。以下の例では6バイトのデータを8文字の文字列に変換しています。元の6バイトのデータは、エスケープシーケンスが必要な内容を含んでいるためソースコード上では9文字必要ですが、変換結果は常に8文字の文字列となり、文字数が減ったことになります。ただし、元々エスケープシーケンスが不要な値であっても、常に3バイトを4文字の文字列で表現するため、3文字で表現可能なバイナリデータを4文字で表現することも頻繁に発生します。したがって、文字数を減らすという観点ではあまり優れているとは言えません。

>>> base64.b64encode(b"a\0\rb\n\t")
b'YQANYgoJ'

ソースコードに記述可能なあらゆる文字を使う

Pythonの文字列定数として利用可能な文字を列挙する

base64は、64種類の文字だけを使ってバイナリデータを表現する方法です。1文字につきちょうど6ビットの情報量が得られるため、わかりやすいというメリットがありますが、64種類の文字以外にも%や&などエスケープシーケンスが不要な文字があるため、より多くの情報を1文字で表現できるはずです。そこで、どれだけの情報が1文字で表現できるかを探求しました。ただし、ここでいう1文字は、UTF-16で2バイトで表現できる範囲内に制限されます（これはCodinGameにおける文字数の数え方の挙動であり、他の基準も考えられます）。UTF-16では、文字をUnicodeのコードポイントで表すと0～65535の範囲になります。ひらがななどの文字は見た目上1文字として扱われますが、絵文字の多くは2文字として扱われます。以上を踏まえて、より効率的なデータ表現方法を探求します。

Unicodeのコードポイント0から65535に相当する65536種類すべての文字を埋め込めるかというと、実際にはそう簡単ではありません。この範囲には、改行文字のほか、特定の役割を持つ文字が含まれており、これらをソースコード中に含めるとエラーが発生する可能性があるためです。どの文字が文字列定数に埋め込めるかを検証するため、ソースコードを自動生成しました。以下がその内容です。候補となる文字を文字列定数に挿入し、文字のコードポイントを取得するord関数を使用して、それが想定通りの値を表現しているかを検証します。なお、ソースコードはUTF-8エンコーディングで保存します。

s="あ"
assert ord(s) == 12354

その結果、65536種類の文字のうち、63483文字が利用可能であることが分かりました。これらの文字をテキストファイルに列挙し、VSCodeで開いた場合のスクリーンショットを示します。

文字列定数に埋め込み可能な文字の列挙結果

見た目が少し怖いですが、通常のプログラミングで使われることはほとんどない制御文字（SOH=0x01、STX=0x02など）を含む文字も埋め込めることがわかりました。ただし、外字の領域など、有効なフォントがなく豆腐が表示される場合があります。一方、以下の文字は埋め込めませんでした。

  • U+0000 ヌル文字
  • U+000A 改行文字(LF)
  • U+000D 改行文字(CR)
  • U+0022 "ダブルクオーテーション: 文字列を"で囲っているため生じる。Pythonであれば'で囲うことも可能であり、この場合は埋め込み可能（逆に'が埋め込み不可能となる）。
  • U+005C \バックスラッシュ: エスケープシーケンスを構成するため。
  • U+D800-U+DFFF サロゲートペアを構成する文字であり、単独ではエラー。

Webブラウザに貼り付けられる文字のチェック

CodinGameでは、ソースコードをWebブラウザ上のフォームに記述して提出します。そのため、エディタ(VSCode)からフォームにコピーアンドペーストしたときに文字が変化したり欠けたりする場合があるため、そのような文字は利用できません。このため、検証用のWebページを作成し、ページにはtextareaを設置して、ここに張り付けられた文字列をJavaScriptで読み取り、想定した内容と一致するか確認しました。Windows10上でVSCodeからChromeへのペーストを行い、その結果、U+0000 (ヌル文字)、U+000D (改行文字(CR)：自動的にLFに変換された)、U+D800-U+DFFF (サロゲートペアを構成する文字)以外の文字が利用可能であることがわかりました。ヌル文字があると、そこで文字列が途切れているかのように扱われました。

Pythonの文字列定数に埋め込めるが、Webブラウザに張り付けられない文字は存在しなかったため、前節で述べた63483文字が利用可能であることに決定しました。

base63483への変換

前節で求めた 63483 文字の集合を用いて、base64 のようにバイナリデータを文字列で表現します。base64 では、3 バイトを 4 文字で表現しました。24 ビットのデータを 64 通り=情報量としては 6 ビット相当の文字を 4 つ用いて表現していることになります。63483 は、情報量としては 15.95 ビット (1.994 バイト) となります。簡単に割り切れる値ではないため、何バイトを何文字で表現するか検討が必要です。base63483 では、347 バイトを 174 文字で表現することにしました。この数値の算出根拠を説明します。仮に 1 バイトを 1 文字で表現する場合、1 バイト = 256 通り、1 文字 = 63483 通りの表現が可能です。この場合は表現可能な空間のうち 0.403% しか活用できないことになります。2 バイトは 2562=65536 通りであり、1 文字では表現できません。3 バイトを 2 文字で表現する場合、空間の利用効率は 2563/634832=0.416% となります。この利用効率を極大にするのが、347 バイトを 174 文字で表現する場合で、99.6% の利用効率が達成されます。

バイナリデータを実際に変換するには、まずバイナリデータを大きな整数に変換し、その整数を63483進数で表現することにより実現できます。例えば、3バイトのデータ [a, b, c] （それぞれ0～255の数値）を入力とした場合、まず整数 i = a*256*256 + b*256 + c を求めます。これを63483進数で表現すると、各桁に0～63482の範囲の整数が現れます。各桁の数値に対応する文字を、前節で定めた63483文字の集合から取得して文字列として出力します。この方法によって、バイナリデータを文字列として表現することができます。

実際のソースコードは以下から参照できます。Pythonの整数はもともと大きさに制限がない多倍長整数ですので、簡潔に実装が可能です。また、巨大な文字リストを持たずに、0~63482の値を区間に分割して、区間ごとのオフセットを加算することで文字を算出する工夫を加えています。

github.com

これにより、1文字あたり174/347=1.994バイトの情報量を持ったエンコーディングが可能となりました。

警告が出る文字を除去したbase63481

前節の方法でエンコーディングを行ったファイルをVSCodeで開くと、以下に示す警告が表示される場合があります。

Line Separatorなどを含むファイルを開いた場合のVSCodeの警告

この警告は、U+2028 (Line Separator) や U+2029 (Paragraph Separator) が含まれる場合に発生します。VSCode だけでなく、CodinGame のフォームに貼り付けた場合も同様の警告が発生するため、不便です。そのため、これらの2文字を使わないようにした base63481 を開発しました。この場合でも、347バイトを174文字で表現することができます。さらに1文字を減らすと、63480通りの文字では情報量が不足するため、ぎりぎりの条件です。わずかなデメリットとして、コードポイントと0~63480の連続する整数を変換するテーブルが少し大きくなります。

ソースコードはこちら。

github.com

注意点

Pythonの文字列定数として合法な文字しか用いていないものの、文字列定数が長い場合に以下のようなエラーが起きます。これに対処するには、ソースコードの最初の行に# coding:utf8を記述します。

SyntaxError: Non-UTF-8 code starting with '\xe0' in file *** on line 3, but no encoding declared; see https://python.org/dev/peps/pep-0263/ for details

データ末尾のパディングは考慮されていません。単純に0で埋めてバイナリデータの長さを347の倍数にしています。デコード時にパディングの長さはわかりません。利用可能な文字をすべて使っており、base64における=のような特殊な役割の文字を残していないため、パディングを表現するための文字はありません。表現可能な空間には1ビット未満の余裕があるので、工夫次第でパディングの長さを表現できるかもしれません。ただし、CodinGameにおいてはデコーダのコード自体がソースコードの一部であり、長さ制限の影響を受けるため、デコーダを複雑化させずに元のデータの長さを数値定数として書き込むのが妥当です。

まとめ

CodinGameのソースコードは長さ制限が10万文字に設定されているため、できるだけ多くのバイナリデータを文字列定数内に埋め込むために、エンコーディング方式base63483を開発しました。調査の結果、Pythonコードの文字列定数内には、長さ1の文字として63483種類の文字が使用できることが判明しました。base64のような単純なエンコーディング方式では、1文字あたり0.75バイトしか表現できませんが、base63483では1.994バイトを表現することができるようになりました。

おまけ: ChatGPTによる文章校正

本記事は、このブログでは初めてChatGPTを用いて文章の校正を行いました。

ChatGPTによる校正のやり取り

プロンプトは以下のようにしました。

以下の日本語文を、プログラミング技術を扱うブログの記事に使えるようなわかりやすい文章に校正してください。

<ここに文章>

後続の入力では、以下のように書いてOKでした。

次の文も校正してください。

<ここに文章>

「以下の文章もお願いします。」という指示だと、突然英訳が始まってしまう場合がありました。

日本語校正を行わせるためのノウハウ集というのは見つけられておらず、断片的な情報からプロンプトを作りましたがなかなか便利でした。ただし、意味が変わってしまう場合が時折あったので、生成された文章はよく注意して確認する必要があります。今回は起こりませんでしたが、数字が変わる可能性もあるので元の文と見比べることは必須だと思います。