コグノスケ

強いオセロ

どうやっても圧勝してしまう「最弱オセロ」（リンク）が話題ですが、実はその横に「強いオセロ」（リンク）もあります。URLから推測するにこちらの方が先に作られたように見えます。

名前に偽りはなく、ものすごく強いです。私のような素人の実力ですと50石（ほぼ真っ白）〜64石（全て白）で完敗します。終盤に一気にひっくり返され、全く勝てません。

まともにやっても全く勝てなかったので、どんな手でも良いから、1度でも勝てないだろうか？と試行錯誤するうちに、ちょっとしたクセが見えてきました。このAIは「終盤の大逆転」を重視していて、序盤〜中盤は石数が不利でも無視する傾向があります。

このクセを逆手に取り、中盤戦でとにかくゴリ押しして、白を全滅させる作戦を取ると、ごくたまに勝てることがあります。下記はその例です。

中盤でゴリ押しして勝てたケース

中盤で押し切れなければ負けです。20〜30局やりましたが、これ以外の勝ち方はできませんでした……。

RISC-Vの命令

目次: RISC-V

最近、何かと関わっているRISC-Vの理解のため、エミュレータを書いてみています。先日購入したHiFive Unleashed（2019年5月26日の日記参照）の1st ROMと2nd ROMを拝借して、Linuxがブートする辺りまで作るのが当面の目標です。

スクラッチから作ると辛いので、ARMv5のエミュレータememu（GitHubへのリンク）をベースにして改造して作っています。まがりなりにもARMv5が動いているんだから、RISC-Vも楽勝だろうと思いきや、世の中そんなに甘くありませんでした。

最初にコケたのはUnalignedな命令ロードです。RISC-VのC拡張をサポートする場合32bit境界ではないアドレスから、32bit命令をロードする場合があります。ARMv5ではUnalignedアクセス例外が発生します。

RISC-Vの命令エンコード

まだ完成していないので、現時点での感想ですが、RISC-Vの命令エンコードは比較的わかりやすい気がします。ただ、ブランチ命令のオフセットは、下記のような並びになっていて、不思議な配置です。

RISC-Vのブランチ命令

今まで見た中で一番見づらいものは、C拡張命令のバイナリです、これは異様に見づらいです。しかしC拡張の目的（命令長を削るため16bit長に無理して詰めている）からすると、仕方ないでしょうね。

C言語とCPUアーキテクチャと除算命令

目次: C言語とlibc

今まであまりCPUアーキテクチャの違いを感じたことはありませんが、除算命令を触っていたところ、アーキテクチャによってかなり動きが違っていて面白かったので、メモしておきます。

プログラムは下記のとおりです。

#include <stdio.h>
#include <limits.h>

void f(int a, int b)
{
        printf("mul:%08x * %08x = %08x\n", a, b, a * b);
        printf("div:%08x / %08 = %08x\n", a, b, a / b);
}

int main(int argc, char *argv[])
{
        f(INT_MAX, -1);
        f(INT_MIN + 1, -1);
        f(INT_MIN, -1);     //乗算、除算の動作は未定義
        f(INT_MAX, 0);      //除算の動作は未定義
}

初めに断っておくと、コメントを打った箇所については、C言語上の仕様上、動作が未定義です。つまり、どんなことでも起こり得ます。不定な結果が返ることもあるし、プログラムが停止することだってあります。

未定義動作も色々

このプログラムをx86 (x86_64, Ryzen 7 2700), ARM (AArch64, Cortex A53), RISC-V (RV64GC, SiFive FU540) のLinux上でそれぞれ実行してみます。

#### x86_64 ####

mul:7fffffff * ffffffff = 80000001
div:7fffffff / ffffffff = 80000001
mul:80000001 * ffffffff = 7fffffff
div:80000001 / ffffffff = 7fffffff
mul:80000000 * ffffffff = 80000000
Floating point exception


#### AArch64 ####

mul:7fffffff * ffffffff = 80000001
div:7fffffff / ffffffff = 80000001
mul:80000001 * ffffffff = 7fffffff
div:80000001 / ffffffff = 7fffffff
mul:80000000 * ffffffff = 80000000
div:80000000 / ffffffff = 80000000
mul:7fffffff * 00000000 = 00000000
div:7fffffff / 00000000 = 00000000


#### RV64GC ####

mul:7fffffff * ffffffff = 80000001
div:7fffffff / ffffffff = 80000001
mul:80000001 * ffffffff = 7fffffff
div:80000001 / ffffffff = 7fffffff
mul:80000000 * ffffffff = 80000000
div:80000000 / ffffffff = 80000000
mul:7fffffff * 00000000 = 00000000
div:7fffffff / 00000000 = ffffffff

当然ながら、動作が定義されている演算は、どのアーキテクチャでも同じ結果です。当たり前ですね。

• INT_MAX * (-1) = INT_MIN + 1
• INT_MAX / (-1) = INT_MIN + 1
• (INT_MIN + 1) * (-1) = INT_MAX
• (INT_MIN + 1) / (-1) = INT_MAX
• INT_MAX * 0 = 0

一方で動作が未定義の演算は、かなり挙動が変わります。

• INT_MIN * (-1) = INT_MIN
• INT_MIN / (-1) = クラッシュ (x86_64), INT_MIN (AArch64, RV64GC)
• INT_MAX / 0 = クラッシュ (x86_64), 0 (AArch64), -1 (RV64GC)

個性が出ますね。

x86の除算命令の奇妙な仕様

先ほどの例でx86上でINT_MIN / (-1) の除算がクラッシュする原因はidiv命令の仕様です。

Intelの命令仕様書（Intel Architectures Software Developer Manual: Vol 2）のIDIV - Signed Divideのページを見ると、保護モード例外 #DEが発生する条件として、

• ソース・オペランド（除数）が0である場合
• デスティネーションに対して符号付きの結果（商）が大きすぎる場合

この2条件が挙げられています。INT_MIN / (-1) は結果が32bitで表現できないため、後者に引っ掛かるわけです。

異常な演算に対して例外を発生させる設計思想なら分かりますが、乗算命令は異常な結果でも素通しなのに、除算命令は異常な結果だと例外発生します。片手落ちの不思議な仕様です。変なの……。

埼玉を洪水から守る

首都圏外郭放水路 庄和排水機場（埼玉県春日部市）の調圧水槽と第一立坑（たてこう）の見学に行きました。

庄和排水機場の外観

首都圏外郭放水路とは、洪水多発地域の中川流域（埼玉県の東部）を洪水から保護するため、中川、綾瀬川といった中小河川の水を地下経由で引き込み、ポンプで引き上げて江戸川に放流する仕組みです。

首都圏外郭放水路の概要

ちなみに国の施設でして、管轄は国土交通省（サイトへのリンク）です。

見学

見学コースの一つである、調圧水槽は、地下神殿との呼び名もあるほどで、広大な空間とたくさんの柱があります。

柱の役割がわかっていなかったのですが、係の方の説明によると、周りの地下水の浮力で調圧水槽が浮き上がってしまうので、重い天井と柱で、水槽を下に押しつけているそうです。

調圧水槽

第一立坑は高さ70mの大迫力で、一番上の壁沿いに組まれた足場から下を見ることができます。私は高いところが苦手でして、非常に怖かったです。足が進まないし、変な汗が止まりません。

怖すぎて壁際にずっとしがみついていたため、写真を撮る余裕がありませんでした。一緒に行ったみなさまが高いところが平気なようで、写真をバシバシ撮っていましたので、一枚恵んでもらいました。

第一立坑（たてこう）

高いところ（立坑）はもう懲り懲りですが……、今回参加したコースとは別の見学コース（排水ポンプ室に入れる）もあるらしいので、別コースにもぜひ行ってみたいですね。