(/^^)/⌒●~*$ a(){ a|a& };a

きょうと…のだいがく?にかよってるんですけど!

ISUCON7本戦でBigintを殺したかった話

注意:このブログではGo言語のBigint(多倍長整数)について触れています
12/6 追記:殺せました

こんにちは。 ISUCON7本戦に「百万円ドリブン」の一員として参加しました。 メンバーは僕と, @nakario, @aokabi の三人で,二人はサークルのメンバーです。 集中のあまり美味しいお昼のクッキーと珈琲は逃してしまいました。

結果はタイトルの通りであり、競技時間内ではネックとなっていた Bigint を殺すことが出来ず、 悔しかったのでBigint周りで試行錯誤をした結果について述べます。 具体的には、Bigintと__float128について述べます。

今回のボトルネック

ボトルネックの測定と発見は @nakario が率先してやってくれました。 僕の改善担当箇所はそれにより判明したボトルネックの一つ 「Bigint の10進上位15桁の取得」 でした。

初期実装

初期実装では、Bigintを一旦文字列に変換してから先頭から15文字をとるという実装になっていました。 ベンチマークを回すと分かるのですが、このBigintは15万桁程度まで達する可能性があり、 すなわち15万文字の最初の15文字のみしか使わないということが平気で起こり、 遅いのも容易に理解できます。これは改善しなければなりませんね。

改善案

Go言語ではBigintはuint(符号なし64bit整数)の配列として表現されています。 単純に思いつく改善方法は、上位15桁さえ分かればよいので、 その配列の上位2つのuintからその数字を近似して計算する方法です。 例えば、 45桁の整数 111112222233333444445555566666777778888899999
= 326529 × 2128 + 8741109308212120013 × 264 + 7629705161560292767
となっているわけですが、これを上位2つのみを使用し、
326529 × 2128 + 8741109308212120013 × 264
= 111112222233333444445555559037072617328607232
と近似します。 計算すれば分かることですが、桁が増えても上位2つのみを用いればよいことに変わりはありません。 上位2つを用いて近似することにより、桁数オーダーだった部分を改善することが出来ます。 こうすれば BigIntを一つも使わなくてもよくなり、大幅な改善が見込めますね。

実装と精度の問題

上記の案をそのままuint64やfloat64で計算すると桁は容易に溢れるので、 log10 して計算し、最後に10の指数で戻せばよいです。楽勝ですね。



なーんてことは無かった…。 そもそもfloat64は15.9桁までしか整数との1対1対応を保証してくれません。 今回必要な桁は15桁、かなりギリギリです。 log10したり演算をすると、微妙に2桁程度合わないのです…。 ISUCON中ずっと「あと2桁!!あと2桁なんや…!!」って叫んでいました。 本質的に精度が微妙に足りないのです。 このあと僕は迷走してしまい、ISUCONは敗北を期しました。

こたえ

15桁全てを合わすことは到底不可能でも、それが何桁かどうかは精度の問題なしにすぐに計算できます。 よって、桁数を計算しもとのBigIntからその10の桁数分で除算するという方法がとれます。
例えば 111112222233333444445555566666777778888899999 / 100000000000000000000000000000
を行い 111112222233333 にするような感じです。 本質的にはBigIntをStringに変換する処理がBigInt除算の処理に変わります。 実はこれだけでかなり高速になり、 初期実装からこの部分のみを変更してベンチマークを走らせたところ、(ネックは他にもあるので一概には言えませんが) 7000点程度だったものから14000点まであがり、スコアが二倍になりました… はいbigintゲーwwwwwwwwww

bigint許さん

しかしながらこんなにも僕を困らせてくれる bigint 、殺すしかありません。 なんとしてでも bigintを実装から全て消し去り心の平穏を取り戻したいものです。 さて、僕の最初に思いついた実装方法は、精度が足りなかっただけなわけですから、 もっと精度の高いものを使えばbigintを使わなくても実装できるはずです。 残念ながら Go言語には float64までしかありません。 float128くらいまであればよいのですが…



はい、というわけで GCC の __float128 を使ってみましょう。

__float128

__float128 の枠組みは、疑似四倍精度とも呼ばれ、ソフトウェア的に float64を複数用いることで 擬似的に4倍精度を達成する枠組みです。 gccコンパイルすれば簡単に使えるので、Go言語とC言語を繋ぐ cgo を用いれば上手くできそうです。 cgo では、C言語コンパイルしたい関数を書いたC言語のコードを用意し、 そのインターフェースとコンパイルフラグ等をgo言語でシュッと記述すると簡単に二つを繋ぐことができます。 以下にCとGoのコードを載せます。

#include <math.h>
#include <quadmath.h>
typedef unsigned long long UINT64;
void myb2e(UINT64 w1,UINT64 w2,UINT64 bef,UINT64 *o_keta,UINT64 *o_res){
  __float128
    fw1 = w1,
    fw2 = w2,
    log10ed = (64 * bef) * M_LN2q / M_LN10q
              + log10q(18446744073709551616.0Q * fw1 + fw2),
    res = expq((log10ed - floorq(log10ed)) * M_LN10q) * 100000000000000.0Q;
  *o_keta = (UINT64)log10ed - 14;
  *o_res = res + 0.000000000000001Q;
}
package main
//#cgo LDFLAGS: -lquadmath
//#cgo CFLAGS: -O3
//#include <stdlib.h>
//typedef unsigned long long UINT64;
//extern void myb2e(UINT64 w1,UINT64 w2,UINT64 bef,UINT64* o_keta,UINT64* o_res);
import "C"
func B2E(w1, w2, bef uint64) (keta, res uint64) {
    var o_keta C.UINT64
    var o_res C.UINT64
    C.myb2e(C.UINT64(w1), C.UINT64(w2), C.UINT64(bef), &o_keta, &o_res)
    return uint64(o_keta), uint64(o_res)
}

はい。bigintを殺せました。勝利ですね。 早速ベンチを回しましょう…。




6 0 0 0 点!!!

初 期 実 装 よ り 遅 い !!

イヤイヤイヤイヤ、オイオイオイオイ… cgoのオーバーヘッドが意外と大きいのか?と思って計測してみましたが、 そういうわけでもなく、純粋に __float128 が遅いようです…。まじかぁ…

まとめ

BigIntを殺そうとしたが結局BigIntを完全に殺すことはできなかった。 BigIntくんも__float128くんよりは生かす価値があるようだ、命拾いしたな…

この記事を読んだ人はこんな記事も読んでいます

aokabit.hatenablog.com

nakario.hateblo.jp

全コード

github.com

12/6 追記 (実質Bigintを殺せた)

Bigint同士の除算は桁数オーダーの時間が掛かりますが、 初期実装の段階では上記の改善のみでよさそうです。 この後、更に高速化してもう一度この部分がネックになってきた場合には、除算を上位の3つのuintのみで行えばよいですね。 この実装であれば実質BigIntを殺したといっても過言ではないのでかなり満足です。

// 桁数が増えても大丈夫
func customBigIntDiv(a *big.Int, b *big.Int) int64 {
    alen := len(a.Bits())
    if alen < 4 {
        return big.NewInt(0).Div(a, b).Int64() 
    }
    an := big.NewInt(0).SetBits(a.Bits()[alen-3:])
    bn := big.NewInt(0).SetBits(b.Bits()[alen-3:])
    return big.NewInt(0).Div(an, bn).Int64() 
}

isucon7学生枠で予選通過してしまった

はじめに

@nakario_jp と @aokabit との3人で組んだチーム名 百万円ドリブン で スコア48,950、全体順位76位、学生9位で予選を通過してしまいました。

通過できたのはメンバー二人のおかげです。 Golangのプロ @nakario_jp がGoをチューニングし、 @aokabit先生がmysqlとnginxをチューニングしていたなか、 僕はよしなに環境構築とかベンチ周辺やログ取った後は踊っているみたいな分担だったので…。

社会人と学生でかなりの力の強さの違いを実感しました。 しかし我々のようなisuconに触れる前までサーバーサイドチューニングをしたことがなかった 初心者でも学生枠なら通過出来る可能性が本当にあったんだなあということで、 これからisuconをやってみたいと思う学生のために、備忘録的に記事を書こうと思います。

したこと

isucon講習会に参加した

isucon.net とりあえずメンバー全員右も左も分からなかったので講習会に参加することにしました。 完全抽選制で僕だけ受かったので知見を得に行ってきました。 このイベントはisuconのやり方を完全に教えてくれる上に、 交通費・懇親会費まで全て支給してくれる最高のイベントなので是非行きましょう。 sshの仕方が分からない人すらもサポートしていたのでどんな初心者でも迷わず行きましょう。

ついでに東京に行けたので東京で @joisino とキンプラを見ました。

twitter.com ちょうどこの日から応援上映の4DX版が公開されたということで一緒に見たのですが、 応援上映に加え4DXで没入感が半端なく、脳の処理速度を超える体験が出来たので最高でした。 isucon講習会に行った後は是非応援上映も行きましょう。

isucon3,4,5 + pixiv社内isucon を練習した

やはり過去問は大事です。 幸いなことに各種 ansible、各種 ami、各種 VagrantFile が整備されているので簡単に行なえます。

isucon3,4

全員が個別のVagrant環境で練習しました。 本家のmasterブランチのものは上手く動作しなかったので別の人のforkしたものを使用しました。 プロビジョニングにはやばい時間がかかることが分かってよかったです。 初めてということで学ぶことがいっぱいで、ボーダーたけーとか言ってました。

isucon5

AWSを使ってみました(isucon5 は実はGCPだったのですが…)。 適当にコミュニティAMIを探したら、isucon5q-ubuntu16.04 みたいな名前のそれっぽいのがあったので やってみたところisucon5はubuntu15.04だったのが原因で上手く動作しないみたいな事が発覚して騙されてしまいました。

仕方がないのでubuntu15.04のインスタンスを立て、一からプロビジョニングをするということをしていたところ、 10時半練習開始のはずが気づいたら16時みたいなことになっていました…。 やはりプロビジョニングには時間がかかりますね…。

サークルの部室でこれをやっていたところ、別の部員に「こんなに環境構築に時間が掛かるなんてこのチームは雑魚では…」みたいに 思われていたようであちゃーという感じでした。

この回は、ファイル権限とか気にせずに管理出来るようにしようぜと

sudo chmod -R 777 / 

を打ってしまったところで全てが終了してしまったのが印象に残っています。

(具体的に言うと sudoコマンドが777になり、sudoの危機管理機能が働いてsudoを打てなくなり、全てが終わります。)

pixivisucon

isucon6は講習会でやっていたので、pixiv社内isuconを練習としてやりました。 今回は公式amiが提供されており、すぐにAWSで開始することが出来ました。 このisuconはpixivらしく画像の配信がネックになっている問題という設定でした。 そういう意味では今回のisucon7もこれと似た問題設定だったので直近にpixivisuconを出来たのは かなり勝因に寄与していると思います。

この回は、git管理のメンバーの意思疎通が取れておらず、 あるメンバーは3層に分けた管理(最奥のウェブアプリのみremoteあり)を想定していたのに、 あるメンバーは1層管理(remoteあり)を想定しており、 気づいたら3層のうち2層が同じremoteを指しているという状況になっていたのが印象的でした。 (具体的に言うと、.gitのobjectファイルがおかしくなり、力技で解決は出来るのでなんとかなったりはします。)

├─ .git/
│  ├─ .git/  ───┐ 
│  │  ├─ .git/  ───:: 同じ remote 
│  │  ├─ ...

まとめ

  • 過去問をやったことで本番でいい感じに出来た
  • goのプロがいたのでgoのオンメモリチューニングなどが爆速に出来た
  • sudo chmod -R 777 /深層.gitなどを事前に経験したので本番で失敗しなかった

最後にはチームメンバーでサイゼで叫びました

高垣楓さんを追って ~クレイジーサイコバス 十津川くまの特急~

行程

f:id:CHY72:20171001225413p:plain

ことの発端

7月くらいに こういうツイートを見ました。

毎年ママチャリで数百キロくらい回るのが習慣になっており、熊野古道チャレンジしたかったのですが、流石に厳しいので断念していました。 …しかし、夏休みが終わってしまうので急遽どこかに行きたいということで @suzusime と熊野古道(熊野本宮大社,那智)に行く今回の旅が幕を明けたのでした。

9/25

この日の夜に部室にいた @nonamea774 が 十津川くまの特急 という路線バスの情報を提供してくれました。 この路線バスは、一本の路線で167もの停留所に停車し、奈良と和歌山を文字通り160km縦断するという恐ろしいバスです。 熊野古道に行くのにはうってつけであり、これは乗るしかないわけです。

↑十津川くまの特急に関する最高のサイトであり、 Internet Explorer 6 で、動作確認を行っているようです)。

9/27

十津川くまの特急

9時発の十津川くまの特急に乗り、熊野本宮大社へ向かいます。 このバスの最大の特徴は前述の通り167ものバス停に停留することです。 これはもう、全てのバス停でチェックインするしかないですね。

本宮大社

142番目の停留所がいわゆる熊野本宮大社であり、ここが本日の目的地です。 本宮大社については有名すぎるので割愛します。 熊野古道を歩きたかったので 3.4km程山を越えた先にある温泉まで、いわゆる熊野古道「大日越」を歩きます。

この温泉に向かう熊野古道を渡る間の旅のログを残さずにいたところ、 勝手に生霊に取り憑かれ美少女にTSしたということにされていました。 みなさまもTSしたければ熊野古道へ行きましょう。

新宮

147 番目の温泉で優勝したあと、167番目の新宮まで十津川くまの特急で向かいます。 新宮は和歌山にしては都会でビジネスホテルも沢山あり、当日に予約無しで行っても泊まれるので便利です。 1~167番目のバス停まで全て乗って(厳密には142~147は乗っていない)約5kのコストでした。 路線バスにこんなに長い期間乗るというなかなか激しい体験が出来たのでとても満足でした。

9/28

新宮を一通り観光した後、楓さんの原風景の本拠地 那智へ向かいました。

前日の温泉へ向かう獣道のような熊野古道とは打って変わって、 那智熊野古道は観光地らしい石畳が整備された文明を感じさせる熊野古道です。 程よく人間の手の入った自然というものは綺麗だなあという感想を持ちました。

那智大社那智の滝で楓さんの神秘を感じとりJRという文明を使って京都へ帰宅。 実は新宮で学割付きの京都行きの切符を買い JRの途中下車というシステムを使って那智で降りたのですが、 こういう便利メソッドは使っていきたいと思いました。

最後に

ここではあまり書きませんでしたが旅の詳細な景色などは、 物理学巫女チノちゃん @suzusime がツイートしてくれています。 @suzusimeと、熊野古道の旅の情報を教えてくださった皆様に感謝の礼を捧げます。

最後に、高垣楓さんの熊野古道の紹介無しには熊野古道に行きたいという欲求は沸かなかったと思うので、 旅の最初のきっかけとなった高垣楓さんに最上級の感謝を捧げ、結びとします。

試験期間なのでラズパイでサーバーを建てた

最近は、Amazonの方が安い製品が多いですね。

河原町

ラズパイ3の機運だったので四条河原町のマルツへ。

京都寺町店 | マルツオンライン

実物を目で見てから買いたかったのと、電子工作用の配線がバラ売りされているのを購入したかったのと すぐに手に入れたかったのがあったので自転車で。

ラズパイにも種類が色々あったが、一番安い element14製のものを購入(4400円)。

サーバーとしてずっと刺しておくわけなので 5V/2.5Aの充電器も購入(1790円)。

ついでに近くに業務用スーパーがあったので業務用サイズのカルピスと梅酒を購入。

ついでに近くのじゃんぱらとかで色々眺めました。

百万遍

ラズパイのOSを焼いたりデータを保存するためのマイクロSDを生協で購入(1080円)。

動かない可能性があるとかブログで読んだことがあったので、RPi SD cards - eLinux.org にOKって書いてあるやつを選択。

常稼働するものなのでバックアップをrsyncしておこうと思い、USBを生協で購入(980円)。

ついでにTOEICも購入。

HDMIが刺さるテレビとケーブルは持っていたので省略。

USBキーボードを持ってなかったので部室から拝借。

1000円くらいのスピーカーも購入。

総額 9200円。

自宅へ

SDカードにOS(Raspbian Jessie Lite)をいい感じに焼きました。

Download Raspbian for Raspberry Pi

デスクトップ画面が欲しかったら、Raspbian Jessie with PIXEL なのですが…。

のなさん(@nonamea774)とそすうさん(@_primenumber)からはArchLinuxを勧められましたが、はじめてのラズパイだったので 資料が多いRaspbianにしてしまいました。 今度データが壊れたらArchLinuxにしようと思います(こう書くとデータを壊しに行きますと言われます(怖い界隈だ))。 そすう先生曰く、ラズパイは64bitなのでそれを最大限活かせるのはArchLinuxだそうです。ほえ〜。

はい。

設定

パスワードとかファイルシステムとかユーザー名とか、初期設定のままだと微妙そうなことをいい感じに調べて設定。

USBに定期的にrsyncでバックアップを取る設定をいい感じに調べて導入。

手っ取り早く音を鳴らしたかったので、 AquesTalkPi をapt-get してゆっくりボイスをコマンドラインから確認。

Dasherをnpmして、Amazon DashButton から青汁を無限に架空に注文できるように。

f:id:CHY72:20170131073829p:plain

SSH目覚まし

crontab で 0 0 * * * mpg321 ~/Music/hoge.mp3 を設定し、 0時(UTC)に自動で音楽がスピーカーから流れるように設定。 置く場所を手の届かない場所にすることで、 ラズパイにSSHしてkillしないと止められないようにすることで 強制的に目覚める圧倒的モダンな仕組み。

サーバー作成

nginx をapt-getしてサーバーを建てた。

Wifiルーターのポートフォワーディング設定をして、httpの80番をラズパイに通すようにして外からも見れるように設定。

グローバルIPアドレスは変わりうるので、無料のDDNSをmydnsでいい感じに調べて設定(http://mydns.jp/)。

これで、http://無.0am.jp からhttpがラズパイにつながるように。

#gacha

f:id:CHY72:20170131072459p:plain

KMCのSlackで全てのチャンネルからSSRの出る確率(1%)で発言を、 {Co,Cu,Pa}のSSRのフレーム(kurimotz氏作)を合成して拾うチャンネルを作成。 画像をPythonのPillowを使っていい感じに合成した後、UIDに依存するsha256したURLを作成し、 ラズパイサーバーに保存して投稿することで、外部画像保存サーバーを使わずに完結。

画像保存サーバー

せっかくなので、h5ai を導入し、見た目を圧倒的モダンにして、描いた作品の数々を公開するページを作成。

激エモ〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜。

KMC超人ロック

この記事は、 ボドゲ紹介 Advent Calendar 2016 - Adventar の22日目の記事です。 前回の記事は、『HIT Z ROAD』と『ヴィア ネビュラ』について - Boardgame Bonus Trackでした。 この記事では、超人ロックについて書かせてもらいます。

ボードゲーム超人ロック」とは

漫画家 聖悠紀氏 の手がける「超人ロック」という漫画があります。 この漫画は、最強の超能力者「ロック」が主人公として宇宙で起こる事件を 解決したりするSF漫画です。 このボードゲームは、この漫画の16巻くらいまでをベースにして作成されました。 このゲームは少なくとも1980年後半頃までには販売され、 1990年頃には既に絶版になっています。 しかし、京大マイコンクラブでは世代を超えて受け継がれ、 2016年の今でも盛んに遊ばれています。 前述のように30年くらいもの歴史があるゲームですから、 宗派に近いものができていて、僕の知っている限りでは現在 京大マイコンクラブ、京大RPG研、名古屋大学のサークル… などのサークルで受け継がれ、独自の洗練されたルールで遊ばれているようです。 このゲームにもともと登場するキャラクターは25人程度なのですが、 名大ロックでは150人ものキャラクターが登場するらしいです。

以降は原型に最も近いと言われる、僕が所属している京大マイコンクラブルールでの運用について書きます。 京大マイコンクラブのルールは、他のルールとくらべて原盤のルールを最大限尊重しているらしいです。

遊び方

このゲームでは、プレイヤーは3つのチーム「Good」「Evel」「Special」に分かれます。 また、主人公である「超人ロック」が Good として必ず一名が参加することになります。 Good陣営はEvel陣営の基地を破壊することが、Evel陣営は基地を守ってGoodを殲滅することが、 Special陣営はそれぞれ個人個人の勝利条件を満たすことが、このゲームの目的になります。

簡単にゲームの流れを説明すると、最初に「惑星編」と呼ばれるステージをプレイし、 役に立つアイテムを集め、次に「秘密基地編」と呼ばれるステージで 基地をめぐる攻防が行われる、という感じです。

このゲームは所謂正体隠匿系ゲームです。 序盤で正体がバレると大抵の場合不利になるので、 最初は自分の能力を使わなければならない時でも 過小に宣言することが多いです。 後半になるにつれ、徐々に情報が集まっていき、 パーティを組んだり、あるいは裏切りを起こしたりしながら 自分の勝利条件を目指します。

f:id:CHY72:20161226005756j:plain

⬆京大マイコンクラブの超人ロック。経年劣化を抑えるため、 カードを自作しスレーブに入れてプレイしている。

ゲームの雰囲気

このゲームでは個人個人がそれぞれ勝利を目指します。 面白いことに、場合によっては一人以外全員勝利することが起きたり、 逆に一人だけが勝利する所謂「S級勝利」が起きたりします。 各人が自分の勝利を目指し徒党を組んだり裏切りを起こしたりする様は、 とても楽しいものです。

ここでは一度簡易シュミレーションをしてゲームの雰囲気をみてみましょう。 まず、6人全員に自身の隠匿するキャラクターが配られます。 キャラクターは25人程いるのですが、その中からバランスがよくなるように配られます。

今回は。「ロック3」「ヤマキ2」「ナガト」「ライオット」「Sスト」「ジェシカ」 のようです。 ロック3、ヤマキ2はGoodなのでEvelの基地を破壊することが目的で、 ナガト、ライオットはEvelなのでそれを阻止することが目的で、 SストはSpecialであり、「ロックを自分で倒す」ことが目的で、 ジェシカもSpecialで「独身男性とパーティ組んで最後まで生存する」ことが目的です。 まずは正体を隠しながら惑星編でアイテムを集めます。

f:id:CHY72:20161226005948j:plain

⬆惑星編。アイテムカードをそれぞれ頑張って回収していいアイテムを集めるフェイズ。

それぞれ、以下のようなアイテムを入手したようです。

  • ロック3:手下、エネ吸3、クローン
  • ヤマキ2:手下、ニケ、Pスーツ4、ジャマー4、ラフ7
  • ナガト:ラフ56、クローン
  • ライオット:クローン、ワイルドカード、Pスーツ5
  • Sスト:船、Eスーツ、エネ吸4、ジャマー3
  • ジェシカ:アフィ、フィールド4、スラム街

例えば、クローンは強いアイテムで、なんと戦闘によって死んでしまっても生き返ります。 他にも、船があれば場外から船(宇宙船)からの攻撃を毎ターン追加で行えることができます。 エネ吸(エネルギー吸収ボール)があれば、運が良ければ相手を数ターン何もできなくできます。

この後の基地編ではそれぞれが互いの思惑を利用しながら 長い長い戦い*1が行われるでしょう。

f:id:CHY72:20161226010045j:plain

⬆秘密基地編。基地をめぐる攻防が行われる。

面白さ

一つのアイテムが戦局を大きく変えることも日常茶飯事という ゲームバランスなので、毎ゲーム全く違ったゲームを楽しめます。 登場しうるキャラクターも25人いるため、毎回違ったゲームを楽しめます。 プレイヤーはたいてい25人の情報は覚えていることが多いので、 判明した能力などからメタ的にキャラクターを推測することが可能で、 それがゲームの面白さを更に引き上げています。

個人的にこのゲームの一番の面白さをあげるとするなら、 なんといってもそのゲームバランスだと思います。 ゲームというものは、「運」、つまりランダム性がバランス良くあると とてもおもしろくなります。 将棋や囲碁などの運要素の全くないゲームもそれはそれで戦略ゲームとして面白いのですが、 ロックは要所要所で「運」が占めるバランスが非常に大きく歓喜したり絶望したりできるのが とてもおもしろいのです。 このゲーム、基本的には経験的に培われる最適な戦略をとるほど勝ちやすくなるゲームなのですが、 例えば死んでしまったキャラクターが、毎戦闘ごとに行われる「実は生きていた」チェックで 1/36の確率で体力Maxで生き返ったり、この攻撃で死ぬ…という攻撃で変身チェック(与えるダメージは、 ダイスを二個降った値によって変わり、そこでピンゾロなどが出ると行われるチェック)で キャラクターが転生(!)して別のキャラクターとしてゲームをプレイすることになったり、 低い確率で起こる奇跡的な出来事が戦局を大きく変えるという「運」に依存した側面ももち、 ゲームの開始から終盤までチャンスがずっと転がっているゲームでもあるのです。

さいごに

いかがでしたでしょうか。 少々駆け足で説明してしまったので雰囲気程度しかつかめなかったかもしれません。 京大マイコンクラブでは KMC超人ロック公式ホームページ というサイトにて 詳細なルールを公開しています。 もしも興味を持っていただけたならば、 京大マイコンクラブに入部(京大マイコンクラブでは入部制限はありません!どなたでも入部できます!) して、是非一緒に超人ロックを遊びましょう。

*1:一ゲームおよそ3時間位

Pietでカラーゴルフ(有彩5色+白)をした

この記事は KMCお絵かき Advent Calendar 2016 - Adventar の 19日目*1の記事です。 前回の記事は @kurimotz による 【クリスマス】「クリスマスケーキ」イラスト/Motz [pixiv] でした。

はじめに 〜経緯〜

KMCでは描け麻雀というものを不定期で行っています。 描け麻雀は、勝者が敗者に好きなお題の絵を描かせることが出来るという麻雀です。 8月頃にこの描け麻雀を行ったのですが、僕が絵を描くのをずっとサボってしまい *2、 この12月に、4ヶ月遅れでこのように提出する運びとなりました。

このときのお題は「輿水幸子」「すずしい」でした。 お題が出されたのは8月だったので、「すずしい」というお題がでるのも頷けます。 8月にとった涼しげな仕事を12月に遅れて幸子が嫌々やらされる…みたいな絵を描くのも頭を よぎったのですが、結局Pietを描いてしまいました。*3

つくったもの

Pietで絵を描くのは過去に何度もやったことがあるので、 今回はいつもと違う制限をつけて描いてみようと思いました。

Pietは 有彩色18色 + 白黒 の計20色 によって 計17の命令が使える高級な言語なのですが、 実は理論上は上手く有彩色5色を選べば、全ての命令が表現できます*4。 プログラミング界隈ではコードゴルフというコードの短さを競う遊びがあり、 Pietではコーデル数の少なさ=コードの短さがよく部内でも競われています。 Pietの場合は別の方面、つまり色数の少なさ(カラーゴルフ)で競うこともできるのですが、 この方面に関してはKMC内ではあまり研究は盛んではなく、 どのようなものが出来るのか気になったのもあり、このようにやってみることにしました。

完成品がこちらです!! f:id:CHY72:20161224000119p:plain 実行すると「すずしい」と出力する、涼しい顔で締め切りを破る輿水幸子です。

(Pietの仕様を十分に満たしたUTF16のPiet処理系で正常に動作します。 (例えば、PietDevでは「要素数の足りないrollでスタックの先頭を消費する」という仕様に沿わない実装があるので動作しません。 未定義な処理は、「何もしない」というのがPietの正しい仕様なのです。dama氏のPidetや 自作のUltraPietでは正常に動作します) )

ひと目で分かる解説

f:id:CHY72:20161224162722p:plain 「いしずす」の順でスタックに積み、最後に逆順に出力しています。

カラーゴルフについて

色が少ないことによって以下のような制約ができます。

  • 黒を使用しない場合、方向転換、終了処理がかなり面倒くさくなる。
  • 基本的に一つの命令は一つの遷移にしか割当たらないので、欲しい命令を実行する時にその色遷移を頑張って作る必要がある。
    • 今回の場合 例えばduplicate命令は黄->紫の遷移でしか表現できない
    • 備考:18有彩色の場合は当然18個の遷移で表現できる
  • 実感として18色フルで使うほうが10倍くらいの情報を詰め込める気がする。
    • 今回の絵くらい大きければ、「もしも締め切りに間に合わなかったら桜の木の下に埋めてもらっても構わないですよ」くらいは詰め込められそう。

一応、色が少ないことで以下のようなメリットはあります。

  • ファイルサイズが小さくなる。
  • 色が多くないのでデザイン的に綺麗なものが出来る*5
  • 達成感がある。

今回の幸子の絵により、5色カラーゴルフは十分に可能であるということは示されたと思います。 今後カラーゴルフをする人口が増えることを望んでいます。

Piet用のお役立ちプログラム

今回の特殊なPietを描くにあたって実装したプログラムを公開します。 まず、絵を一番近いPiet18色に変換するプログラムとして

topietcolor.py · GitHub

をPython3で書きました。 まず下絵を描いてそれを徐々にPietにしていったのでこういうプログラムは大事です。

次に、どの5色を選べば17命令を達成できるかを調べるプログラムとして

search_piet5.cpp · GitHub

C++で書きました。 結果的に17命令を達成できる5色の選び方は4通りあることが分かりました。 このプログラムの結果から使用する5色を決めて書きました。

さいごに

もしも間に合えばこの絵のメイキングについて、 コミックマーケット91の サークル「いっと☆わーくす!」に、 寄稿しようと考えているので、コミケに行かれる方は是非手に取ってくださいまし。

明日*6の12/20のアドベントカレンダーは、@maztani による 【KMCお絵かきAdventCalendar】Illustrator で星輝子 - mz-log です。 彼はめっちゃすごい。

f:id:CHY72:20161224000119p:plain

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.
f:id:CHY72:20161224174930p:plain

*1:5日遅れ…すみません

*2:描いていない間は他の描け麻雀に参加できないという制約はあるのでどんな人でもいずれは描く

*3:Piet絵師自体が絶対的に少ないので描く意味はあるはず!!

*4: (4+3+2+1)*2 > 17

*5:ある事物を表現する時に色は少ないほうがいいですよね

*6:明日…