2022年1月1日土曜日

OpenCVでサイゼリヤの「超難解 大人の間違い探し」を台無しにする



 あけましておめでとうございます。


先日、久々にサイゼリヤで外食をした際、レジにて間違い探しを配っているのに気づきました。自分がこれを手にした瞬間に頭のなかで間違いを見つけるプログラムができたのですが、数日後の深夜に実際にコードに落として、動くものができました。

今回は、どのようにしてこの出力を得たかについて、具体的なコード例とあわせて紹介します。


基本的な考え方

サイゼリヤの間違い探しは、左右反転した状態で絵の違いを見つけるものです。今回はAKAZE特徴量を用いてふたつの画像を重ね合わせた上で、差異部分に色をつけてマークしていくことにします。


入力画像を用意する

今回サイゼリヤで入手した間違い探しはA4サイズのコピー用紙に印刷されたものです(配達のときに同梱したりしているようですね)。後でAKAZE特徴量のアルゴリズムで取り扱うため、きちんと平面がでた状態でスキャンします。



今回は手元にあったドキュメントスキャナ(Canon ImageFormla DR-C125)を使いましたが、きちんと平らにできれば、携帯電話のカメラを使ったりしてもいいですし、コンビニのコピー機で適当な形式で保存してきても構いません。

また、ソースの特性を考慮し、可能な限り、白・黒に二値化します。必須ではないのですが、これをしておくことで後の処理がしやすくなるでしょう。二値化はPhotoshop, GIMPなどの画像編集ツールやドキュメントスキャナのスキャン時設定にて行えるでしょう。

入力画像を2ファイルに分割する



img1.jpg, img2.jpg として対象の画像を保存します。今回は macOS 標準のスクリーンショット機能を用いて、とても雑にファイルを生成しました。後でAKAZE特徴量を用いて重ね合わせるつもりですので、ここで傾きや大きさ、ピクセルのシフト量など、正確さを求める必要はありません。今回は JPEGを使用しましたが、 OpenCV が対応する形式であれば PNG などでも構いません。


作業環境

今回は Juypter Notebook 上で、 Python 3.8 の環境に OpenCV 4.x をインストールし作業していきます。 OpenCV は下記操作でインストールするとよいでしょう。 opencv-contrib-python パッケージをインストールすることで、のちに使う AKAZE 特徴量などのアルゴリズムもすぐ使える状態になっています。

!pip install opencv-contrib-python
画像の読み込み
cv2.imread() で画像を読み取って ndarray にします。元画像は原則モノクロですし、面倒を減らすため、読み込み時に1チャンネルのグレースケール画像としておきました。このほうが後での画像のマッチングや比較も簡単です。
import cv2
import numpy as np
from math import sqrt
img1 = cv2.imread("saizeriya_akaze/img1.jpg", cv2.IMREAD_GRAYSCALE)
img2 = cv2.imread("saizeriya_akaze/img2.jpg", cv2.IMREAD_GRAYSCALE)

img1 と img2 は左右反転していますので、 img2 を左右反転させておきます。

img2 = cv2.flip(img2, 1)
2枚の画像を重ね合わせる

AKAZE特徴量を使って画像をマッチングします。

akaze = cv2.AKAZE_create()
kpts1, desc1 = akaze.detectAndCompute(img1, None)
kpts2, desc2 = akaze.detectAndCompute(img2, None)
matcher = cv2.DescriptorMatcher_create(cv2.DescriptorMatcher_BRUTEFORCE_HAMMING)
nn_matches = matcher.knnMatch(desc1, desc2, 2)
matched1 = []
matched2 = []
nn_match_ratio = 0.8 # Nearest neighbor matching ratio
for m, n in nn_matches:
    if m.distance < nn_match_ratio * n.distance:
        matched1.append(kpts1[m.queryIdx])
        matched2.append(kpts2[m.trainIdx])
inliers1 = []
inliers2 = []
good_matches = []
inlier_threshold = 1000 # Distance threshold to identify inliers with homography check
for i, m in enumerate(matched1):
    col = np.ones((3,1), dtype=np.float64)
    col[0:2,0] = m.pt
    dist = sqrt(pow(col[0,0] - matched2[i].pt[0], 2) +\
                pow(col[1,0] - matched2[i].pt[1], 2))
    if dist < inlier_threshold:
        good_matches.append(cv2.DMatch(len(inliers1), len(inliers2), 0))
        inliers1.append(matched1[i])
        inliers2.append(matched2[i])

これで img1 と img2(左右反転) 画像の特徴を対応が得られます。これを画像として出力してみます。

res = np.empty((max(img1.shape[0], img2.shape[0]), img1.shape[1]+img2.shape[1], 3), dtype=np.uint8)
cv2.drawMatches(img1, inliers1, img2, inliers2, good_matches, res)
cv2.imwrite("saizeriya_akaze/result.png", res)


コピー&ペーストでソースコードをいじった時に少しおかしくなったように見えるけど、実用上問題なさそうなのでヨシ。

もちろん、間違い探しという特性上、画像が意図的に異なるので、マッチしない特徴もあるわけですが、十分な数の特徴量がマッチすれば、やりたい事に対して問題はありません。

この特徴量をもとに2枚の映像を重ね合わせます。 img1 の位置を基準とし、 img2 が img1 に重なるようにワープフィルタをかけた img3 を得ます。この処理は IkaLog というプログラムから一部を持ってきました。そのため画像名にキャリブレーションイメージ、キャプチャイメージという名前が付いていますが、そのまま利用しています。
Acalibration_image_gray = img1
capture_image_gray = img2
matcher = cv2.BFMatcher(cv2.NORM_HAMMING)


capture_image_keypoints, capture_image_descriptors = \
    akaze.detectAndCompute(capture_image_gray, None)
calibration_image_keypoints, calibration_image_descriptors = \
    akaze.detectAndCompute(calibration_image_gray, None)

print('caputure_image - %d features' % (len(capture_image_keypoints)))
print('matching...')

def filter_matches(kp1, kp2, matches, ratio=0.75):
    mkp1, mkp2 = [], []
    for m in matches:
        if len(m) == 2 and m[0].distance < m[1].distance * ratio:
            m = m[0]
            mkp1.append(kp1[m.queryIdx])
            mkp2.append(kp2[m.trainIdx])
    p1 = np.float32([kp.pt for kp in mkp1])
    p2 = np.float32([kp.pt for kp in mkp2])
    kp_pairs = zip(mkp1, mkp2)
    return p1, p2, kp_pairs
raw_matches = matcher.knnMatch(
    calibration_image_descriptors,
    trainDescriptors=capture_image_descriptors,
    k=2)

p1, p2, kp_pairs = filter_matches(
    calibration_image_keypoints,
    capture_image_keypoints,
    raw_matches,)

if len(p1) >= 4:
    H, status = cv2.findHomography(p1, p2, cv2.RANSAC, 5.0)
    print('%d / %d  inliers/matched' % (np.sum(status), len(status)))
else:
    H, status = None, None
    print('%d matches found, not enough for homography estimation' % len(p1))
    raise Exception()

assert H is not None

if len(status) < 1000:
    raise WarpCalibrationNotFound()

calibration_image_height, calibration_image_width = img1.shape

corners = np.float32(
    [[0, 0],
     [calibration_image_width, 0],
     [calibration_image_width, calibration_image_height],
     [0, calibration_image_height]])

pts1 = np.float32(cv2.perspectiveTransform(
    corners.reshape(1, -1, 2), H).reshape(-1, 2) + (0, 0))
pts2 = np.float32([
    [0, 0],
    [calibration_image_width, 0],
    [calibration_image_width, calibration_image_height],
    [0, calibration_image_height]])

print('pts1: %s' % [pts1])
print('pts2: %s' % [pts2])

M = cv2.getPerspectiveTransform(pts1, pts2)
 
img3 = cv2.warpPerspective(img2, M, (calibration_image_width, calibration_image_height))
これにより img1 とできるだけマッチするようワープフィルタを適用した img3 が得られました。


img1 と img2 の縦横ピクセル数は一致していないのですが、 img1 にあわせてワープフィルタをかけた img3 は img1 と同じピクセル数になっているので、このことを確認しておきます。

こんな面倒なことをしなくても、他のツールを使ってあらかじめ重ね合わせておくことも可能です。ただ、この重ね合わせ処理含めて実装したので、サイゼリヤの間違い探しの新しいバージョンが出ても、入力画像を差し替える以上の労力をかける必要はなくなりました。


画像の差分をとる

img1 と img3 の差の絶対値をとります。これにより1プレーン8ビット(256色調)色調の画像に対して、差がなければ0、差があれば255の値が得られます。なお img1 および img3 は符号なし8ビット整数の1プレーン モノクロ画像ですが、差を取るにあたり -255 ~ 255 までの範囲をとりうるため、 符号付き32ビット整数として扱っています。絶対値をとった時点では 0~255 に収まっているため、 img_abs は 0~255 の符号付き32ビット整数です。

img_abs = abs(img1.astype(np.int32) - img3.astype(np.int32))

img_abs の内容をモノクロ画像として出力した例を参考までに掲載しておきます。 img1, img2 で差があった部分が白く浮き上がっていることがわかるでしょう。



差分強調画像を作成し出力する

最終結果を出力します。ここではimg1を基として答えの画像を作成します。この画像は HSV フォーマットとして扱うことにします。HSVとは Hue(色相), Saturation(彩度)、明るさ(Brightness) の3要素で色を表現します。モノクロ画像をHSV色空間に変換していますので、S=0、V=0~255, Hについては未定義(結果としてゼロが入っているが)という状態になります。

img_bgr = cv2.cvtColor(img1, cv2.COLOR_GRAY2BGR)
img_hsv = cv2.cvtColor(img_bgr, cv2.COLOR_BGR2HSV)

このうち彩度のプレーンを、先ほど得た img1 と img3 の絶対値 img_abs で置き換えます。差のある部分はほぼ 0 、差がある部分だけ彩度があがるため、結果として img1 の画像に対して、 img1 と img3 の差がある部分には何らかの色が付きます。どのような色がつくかは色相チャンネルによりますが、今回 cv2.cvtColor() はこのチャンネルを0で初期化していますので、これに対応して赤色になります。

img_hsv[:, :, 1] = img_abs

生成した画像を cv2.imwrite() で画像ファイルに落とします。 cv2.imwrite() は BGR フォーマットのカラー画像をとりますのでHSV色空間からBGR色空間へ変換も行います。

cv2.imwrite("saizeriya_akaze/result.png", cv2.cvtColor(img_hsv, cv2.COLOR_HSV2BGR))

出力結果


今年もよろしく御願いします。


2021年12月30日木曜日

日本語訳:Apex Legends のALGSマッチを機械学習で解析した件 Using Machine Learning, I analyzed 2.3TB of competitive apex to track everything

This is a translation of Reddit  post Using Machine Learning, I analyzed 2.3TB of competitive apex to track everything into Japanese.

Apex Legends のゲームプレイについて機械学習を用いて分析した結果が Reddit に投稿されており話題になっていました。興味深い内容なので、翻訳サービスなどを用いて読んでいる日本の方も多いと思います。しかし、機械翻訳では判りづらい点もありますので、適当に日本語に翻訳したものを置いておきます。

英語にはあまり自信がなく、誤訳などもあるかもしれませんが、お気づきの点がありましたら @hasegaw までお知らせいただけますと幸いです。

予備知識

この投稿者は統計について研究されている大学院生で、 Apex Legends の ALGS 3大会のビデオから得られた情報をコンピュータに入力したり、もしくは関連するゲーム配信をコンピュータビジョンのアプローチから分析し、下記の内容の論文を書きました。

今回、コンピュータを用いてたくさんのデータを集計し、そこから規則性などを見いだす方法として機械学習(Machine Learning)と呼ばれるものが使われました。これは、最近AI(人工知能)として話題になっている技術のひとつです。

~~~

私は、以下の7つ問いについて分析した。

  • ジブラルタルは再現性が高く、そしてゲームを壊すほどに強力なのか?
  • コントローラ(Pad)プレイヤーは、本当に短距離の交戦を支配しているのか?エイムアシストは効きすぎているのか?
  • リコイルチートを使用するプロプレイヤーは存在するのか?
  • 最適な交戦時間は?
  • 最適な安置移動(Rotation)ははどれぐらいの速度か?
  • 最適なバックパックの構成は?
  • イロ(ELO)レーティングが最も高いプレイヤーは誰か。また、その理由は?


■概要

Kirk Matrix は、サッカーのランキングアルゴリズム Colley Matrix を基にカスタマイズしたものである。また、グループ競技における個人のレーティングのために、 Bradley-Terry ニューラルネットワークモデルを用いた。この方法は、シンプルな統計的原理と変数に基づき、柔軟で、バイアスがないようにしたものである。


わかったこと

ジブラルタル

ジブラルタルは時間あたりのダメージ量が(他のレジェンドより)低く、個人としての撃ち合いによる勝率が低く、受けるダメージ量も大きく、またキルタイム(TTK)が最も短い(訳者注:相手を落とす時間が短いという意味だと思います)。

ジブラルタルは、独立した(他部隊の介入がない)3v3 の交戦において、もっとも死亡しやすい。これは、次点のブラッドハウンドよりも 23.1% 高い確率であった。ジブラルタルは最もフォーカスされやすいキャラクタである。

ドームファイトによる交戦勝率は 50%-50% で、他のチームより特に優れているチームは存在しなかった。ドームファイトは平均48秒で、6人あたり4人がノックされる。

(訳者注釈)ここで言っているのは、接敵でジブラルタルが戦闘でフォーカスされやすく、落ちやすく、1プレイヤーとしての成績が低くなりやすいと統計的データに基づいて説明しているのであって、決して「チームとしての勝率が低い」という話ではありません。

他レジェンドとの入れ替わりもあるが、ジブラルタルのキャラクターとしてのELOは最下位であり、実証データもこれを裏付けている。


エイムアシスト

ALGSにおいては長距離交戦が非常に少なく、中距離交戦とまとめて扱う必要があった。

  1. ドームファイトの交戦勝率: KB/Mouse 54% : 46% Pad
  2. 短距離の交戦勝率: KB/Mouse 52% : 48% Pad
  3. 中・長距離の交戦勝率: KB/Mouse 51% : 49% Pad
  4. ワンクリップシーンでの勝率  KB/Mouse 38% : 62% Pad
  5. KB/Mouse の ADS 振り向き速度の優位性により、混沌としたドームファイトを制することを可能としている。
  6. エイムアシストがあったとしても、 Pad はあらゆる距離での接敵において KB/Mouse に対して劣っているが、一方でコントローラプレイヤーは即時キル(one clip)を繰り返すこともでき、良い結果にも悪い結果にもなる。
(訳者注:KB/Mouse のほうがトータルとしては優れているが、 Pad プレイヤーは下振れもすれば上振れすることも多いということになります)

チーター

驚いたことに、NA/EU/APAC NorthのALGSプレイヤーにおいてリコイルチートを使用するプレイヤーはひとりも検出されなかった。私はこの結果が正しいものと信じている。


最適な交戦時間

交戦時間よりも、サードパーティー(漁夫)がノックアウトを取るうえで大きな相関があると分かった。これは、間違いなく、キルフィード(キルログ)管理、サードパーティー(漁夫)されないこと、敵対チームの把握によるものである。なお、このセクションにおける知見は重大な欠陥があるため、断りなく使用するべきではない。

(※訳者注:要するに、うまく漁夫して、漁夫られないよう気をつけることが大事だとのこと)


最適な安置移動(Rotations)速度

ここでも、私は明確な答えを見つけることができなかったが、興味深い発見があった。 KB/Mouse プレイヤーの移動速度は、 Pad プレイヤーの移動速度よりも平均 6% 速いのである。この違いは、ランドマークからランドマークまで(??)の移動で、壁キック2回、スライドジャンプ4回に相当するものである。 Pad プレイヤーは、これらの動きを追加することにより、(※訳者注:何に対して?)移動を約 16 秒短縮できるかもしれない。


最適なバックパックの構成

残念ながら、こちらも明確な答えを見つけることができなかった。ただし、金バックパックをを持っていることが、Apex Legendsのどのアイテムよりも、勝利と強い相関があった。


上位ELOレーティング

(※訳者注:ELOレーティングとは、平均的な実力のプレイヤーと接敵した場合に予想された勝率に推定したものとされる。Wikipediaによれば対数が使われるとのこと。Redditの投稿にはELOのどこのように算出したかは記述がないが、投稿の最後にあるリンクを読み解けば細かいことがわかるかもしれない)

  1. Ras .9987

  2. Senoxe .9363

  3. Lou .9246

  4. Dezignful .9244

  5. Mo-Mon .8331

  6. Sweet .8075

  7. Genburten .8009

  8. Hardecki .7977

  9. Dooplex .7865

  10. Ojrein .78647

ImperialHalはわずか .00002 の差で次点。

  1. Hal .78645

利用したモデルはRasによって破綻されられるほどで、RasはELO算出に用いられた12の変数のうち11つが並め〜低いのだが、接敵時の移動速度については例外だ。接近戦やドームファイトにおいて、他の ALGS プレイヤーと比較して、Ras はわずか3分の1のダメージしか受けない。

現在のところ、Rasと他の競技者との差は、おもに彼の移動テクニック(※キャラコン)によるものである。他のプレイヤーが同等のテクニックを極めた場合、この差は大きく縮まるかもしれない。


私の経歴について:統計学の学士号、修士号を所得。本内容の論文を提出しており、通過し次第(2~3日)、本分析のグラフやデータを公開できるようになる見込みです。

使用したツールについて:すべてのツールはパブリックに利用可能なものですが、フォークされ、私の特定のニーズに合わせてカスタマイズされています。

〜〜〜

「所詮AIの判断だろ」といった意見もありますが、これは機械学習アルゴリズムを用いてALGSの成績を定量的に分析した結果なので、ALGSという限られたマッチ本数での分析によりバイアスはかかっているのでしょうが、ここに書かれた分析の範囲では、だいたい正しいことだろうなと思っています。

私は以前 IkaLog というスプラトゥーンのビデオから自動的に戦績を解析・出力するソフトを作成し、これを stat.ink というサイトがとりまとめ、蓄積されたデータを基に分析する方もいらっしゃったのを思い出しました。ゲームとはいえ、データを分析して考察するのはとても面白いですね。 Apex Legends に限らず、色々なゲームで、一般プレイヤーのプレイも含めて、このような分析ができると、いろいろと面白いのでしょうが。


おまけ:過去に投稿して話題になったツイートのスレッド。ネットゲームのチート対策は攻撃者のほうが有利で、対策は色々と難しいところもあるということを感じてもらえればと思います(もちろん、マッチしてしまうプレイヤーとしてはたまったものじゃないですが)。

2021年11月3日水曜日

Radeon RX 6800 XT の OpenCL を有効化する (スクリプト化編)

Radeon RX 6800 XT の OpenCL を有効化する に記述したレジストリ操作について、毎回手作業で実施することが面倒なため Python スクリプトに起こした。

#! python

import os
import winreg
 
base_path = r"C:\Windows\System32\DriverStore\FileRepository"


def detect_amdocl():
    amdocl_list = []
    for curDir, dirs, files in os.walk(base_path):
        for file in files:
            if not file.lower() == "amdocl64.dll":
                continue
            amdocl_fullpath = os.path.join(curDir, file)
            amdocl_timestamp = os.stat(amdocl_fullpath).st_mtime
        
            amdocl_list.append({'path': amdocl_fullpath, 'ts': amdocl_timestamp})

    if len(amdocl_list) == 0:
        return None

    amdocl_list = sorted(amdocl_list, key=lambda e:e['ts'])
    return amdocl_list[-1]['path']


def remove_old_values(regkey, latest_amdocl=None):
    i = 0
    while True:
        value_name = None
        try:
            value_name = winreg.EnumValue(regkey, i)[0]
            i += 1
        except OSError:
            # Will be here when the enumeration is done.
            break

        if not value_name.lower().endswith("amdocl64.dll"):
            continue

        if latest_amdocl:
            if value_name.lower() == latest_amdocl.lower():
                print("latest value: %s" % value_name)
                continue

        print("delete value: %s" % value_name)
        try:
            winreg.DeleteValue(regkey, value_name)
        except Exception as e:
            print(e)


if __name__ == "__main__":
    amdocl_path = detect_amdocl()
    if not amdocl_path:
	    raise Exception("Could not determine path of amdocl64.dll")

    reg = winreg.ConnectRegistry(None, winreg.HKEY_LOCAL_MACHINE, )
    regkey = winreg.OpenKey(reg, r"SOFTWARE\Khronos\OpenCL\Vendors",
            0, winreg.KEY_ALL_ACCESS)

    # Delete old values.
    remove_old_values(regkey, amdocl_path)

    # Add a new key.
    winreg.SetValueEx(regkey, amdocl_path, 0, winreg.REG_DWORD, 0x00000000)

    winreg.CloseKey(reg)

    print("done")
    

PowerShell での実装がより理想的かもしれないが。今度 cxFreeze による EXE バイナリ化などを試してみようと思う。


2021年5月28日金曜日

A Puzzle A Day のソルバーを書いてみた(6/20更新)

更新内容

6/20 ... C言語版について追記しました。

面白そうなパズルとの出会い

Twitter で A Puzzle A Day というカレンダーパズルを見かけた。


このパズルは1月〜12月、1日〜31日までのセルがあり、任意の日付(たとえば5月28日だとか6月1日だとか)をパズルを通して表現できる、というもののようだ。テトリスにでてきそうなブロックを組み合わせて、目的の日付にかかわる部分以外をキレイで埋められれば完成。毎日パズルが楽しめるし、1年後に同じ日付の答えを得ようとしても改めて楽しめそうで、とても面白そうだ。

久々に「このパズルは私も欲しい!」と思った。

国内の販売店が普通に売ってるようなものだったらうっかりオーダーしていたかもしれない。どうやらノルウェーのほうでレーザープリンタを用いて作ってるような感じで、持っている人は少ないのではないか。 Twitter タイムラインをみると紙やら木材のレーザーカットやら思い思いの方法で手作りをして楽しんでいる人もいるようで、私も何か作ろうと思った。

その結果として、ソルバーができた。

https://github.com/hasegaw/puzzle-a-day-solver


ソルバー?

ソルバー(Solver)というのは答えを求めるツールだ。たとえば今回のソルバーの場合、5月28日であればこうすると良い感じにブロックがはまりますよ、というのを教えてくれる。このパズルは365通りの目標があるほか、それぞれに複数の解法があるので、趣味などとしてソルバーを書いてみても楽しいだろうと思って、作ってみた。

私はコンピュータサイエンスを学んだエンジニアでも競プロ勢でもアルゴリズムに強いわけでもないので、ここで紹介するアルゴリズムについてはツッコミどころもあると思う。この記事の内容は、とりあえず趣味で簡単なプログラムを書いているだけでも、このパズルのソルバーはこれぐらいの考えで作れる内容だよ、という紹介ということでご理解いただきたい。


ルールの確認

このパズルのボードは下記の構造になっている。



左が、パズルの舞台となる盤面で、ここにブロックを詰めていくことになる。黒色のセルはブロックが置けない場所で、オレンジ色のセルは、一例として5月28日を表現する場合においてブロックで隠れてはいけないセルだ。

右側に示した 8つのブロックを盤面に並べていく。各ひとつ使えるのだが、各ブロックは回転させても良いし、反転させても良いようだ。なので、ひとつのブロックでも盤面上では最大で8つの姿をとりうる。



盤面の黒色セルおよびオレンジのセルに重ならないように、これらの8つのブロックを配置できたらパズルが解けたことになる。


基本的な考え方

ボードサイズは7x7のマトリックスで表現できる。ここで、ブロックを置いてはいけないセルを 1 、それ以外を 0 としたマトリックスを作る。ルール上絶対にブロックが乗ってはいけない部分のみ 1 としたマトリックスの例、それに加えて目的の日付セルも 1 としたマトリックスの例を示す。



ここで黒色セルと日付セルをわけて考えてもよいのだが、候補を見つけていくには、黒色セルおよび日付セルの両方がフラグされている後者のマトリックスが基点になる。

これに対して、特定のブロックを特定の回転・反転・位置の条件で配置する場合に、どのセルにあたるかを示す行列(以後、候補とよぶ)を作成する。ここではふたつの例を示す。


候補がボードにはまるかどうかは、現状のボードの状況を示すマトリックスと候補のマトリックスを加算してみればわかる。整数値の加算結果として 1 を超えるセルが発生する場合は、ブロックと何かがぶつかってしまい、そこに当てはめられない事を意味する。(ここで、後の最適化で触れる論理積を使ってもいい)


当てはめられる候補を見つけたら、再帰的に他のブロックも当てはまる所を探していって、全てのブロックを使い切ったら解法が見つかったことになる。



実際のところ、これを適当に置いていってもブロックが素直に収まってくれる可能性はかなり低い。黒色セルとオレンジの日付セルを除いて全てのセルをブロックで埋めないと答えにたどり着かないことを利用して、マトリックスのふち側のセルから優先して埋める。これにより、隙間の発生により絶対に解法にたどり着けないことが自明な候補を探索対象から外すことができる。



私の実装では左上から右へ、行が埋まったら次の行へ、という順番でセルを埋めるようにしている。次に埋めるセルを見つけるには、ボードの最新盤面におけるゼロのセルを見つければよい。候補がそのセルを埋めてくれるかは、その候補において目的のセルが 1 になっているかを見ればよい。候補が目的セルを埋めなくても解法に繋がる可能性はあるが、後に別のセルを埋める際に改めて評価されるので、ここでは候補から除外してよい。とにかくフチから埋めて、ボード上に隙間ができない候補から試したほうがよいからだ。

これを繰り返していくと、ボード上のセルでゼロがなくなり(すべて 1 になる)、未使用ブロックもなくなっているはずだ。この方法で総当たりしていけば、解法にたどり付ける。

実装については Pyhthon + NumPy を利用した。 NumPy で上記において必要となるマトリックス演算のほとんどが実現できるほか、この後に触れるベクタライゼーションを意識した記述にすることで、さらなる高速化が期待できる。


ベクタライゼーション (Vectorization)

上記のアルゴリズムは、どのようなプログラムで書いてもよい。私は Python を使用したが、別に Ruby を使ってもいいし、 JavaScript/TypeScript でも、 Perl でも、 Golang でも C でも Pascal でも、 C# でも、 Java でも、 BASIC でもなんでもよい。

ただ、このような処理を愚直にループ処理で書いても、コンピュータはこれを速く処理ができない。このため、コンピュータが高速に処理できるような、まとまった行列演算にできるだけ落とし込んでいく。たとえば盤面に対して次の候補を探すためにマトリックスを加算する場合に、まとめて加算をしたほうが速い。

もちろん加算すべきは ボードの現状 × 候補の数 なので計算すべき量は一緒なのだが、 Python コードとして繰り返しを書くよりも、 NumPy などの C 言語ベースで書かれたライブラリ内でループをしたほうが速い。場合によっては、バックエンドのライブラリ内において、 CPU の SIMD 命令で計算することにより、より実行時間を短縮してくれる可能性がある。

具体的には、 10x10 のボードに対して 10x10 の候補が 10,000 あった場合、 Python レベルで10,000回加算するよりも、 10000x10x10 の候補に対して 10x10 のマトリックスを加算するほうが速く実行できる。

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import cProfile
import numpy as np

mat1 = np.zeros((10000, 10, 10), dtype=np.uint8)
mat2 = np.zeros((10, 10), dtype=np.uint8)

mat1[:, :, :] = 3
mat2[::, :] = 3


def func1():
    mat1 + mat2


def func2():
    for m in mat1:
        m + mat2


if __name__ == '__main__':
    cProfile.run('func1()')
    cProfile.run('func2()')

% python bench.py
         4 function calls in 0.000 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 :1()
        1    0.000    0.000    0.000    0.000 bench.py:12(func1)
        1    0.000    0.000    0.000    0.000 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}


         4 function calls in 0.005 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.005    0.005 :1()
        1    0.005    0.005    0.005    0.005 bench.py:15(func2)
        1    0.000    0.000    0.005    0.005 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}


また、大抵の場合、 for ループなどを使用し最小値を探すよりも、 NumPy.argmin() などのライブラリ関数を活用したほうが速い。

このような観点でベクタライゼーションをある程度進めたところ、当初手元のコンピュータ(MacBook Pro 2019, 2.5GHz)では 600秒(10分)かかっていた探索が60秒以内で完了するようになった 。


バイナリ化

ベクタライゼーションにより特定の日付向けの解法が60秒以内に得られるようになったが、もう少し速くしてみようかなと思い、内部表現をバイナリ化してみることにした。

ここまでの作業は (7, 7) の大きさのマトリックスで、各要素は 8bit の整数値として扱ってきた。しかし 7x7 というサイズで、上記アルゴリズムでは基本的に 0 と 1 のみ(衝突検出のみ 2 が登場)で成り立っているので、2進数で表現できる。これにより 7x7=49バイトで表現していた盤面や候補が8バイトで表現できるようになり、メモリ上の表現が7分の1になること、uint64(64ビット符号なし整数)表現でのビット演算は現在のプロセッサだと1命令で実行できる。大幅な高速化が望めるだろう。

盤面の各ビットを以下のように割り当てることにした。最上位ビットから利用して最下位ビット側を未使用にしているのは若干気持ち悪く見えるかもしれないが、当初はブロックをシフトした際の範囲外判定のために右側のビットを残しておこうと思ったのでこのような割り当てになっている(結局使わなかったが)。気に入らなければ後述するルックアップテーブルの値を調整すればよい。

追記)このようにビットアサインするつもりだったが、実際には違うビットアサインをしていた。上記のビットアサイン表は参考例としてそのまま掲載しておく。

既存のソースコードの (7, 7) のマトリックスの内部表現からこのバイナリ64ビットの内部表現に変換するため、以下のような関数を定義した。本格的なループ処理の前後で使われるだけなので、かなり適当な書き方だが、ここでの実行時間は大したことないので問題ない。

def generate_mat2bin_lut():
    lut = np.zeros((7, 7), dtype=np.uint64)
    for y in range(7):
        for x in range(7):
            b = 8 * y + x
            lut[y, x] = base_bit >> (63- 8 * y - x)
    return lut

def mat2bin(mat):
    assert mat.shape[0] == 7 and mat.shape[1] == 7
    lut = mat2bin_lut.copy()
    lut[mat == 0] = 0
    return np.sum(lut) # as np.unit64

def bin2mat(b):
    mat = np.zeros((7, 7), dtype=np.uint8)
    for y in range(7):
        for x in range(7):
            if (b & mat2bin_lut[y, x]):
                mat[y, x] = 1
mat2bin_lut = generate_mat2bin_lut()

二進数について理解している人なら(もっといいやりかたがあるよという指摘はいくらでもあるだろうが)何をしているか判ると思うので、詳細は省略する。

これで mat2bin() によりマトリックス表現からバイナリ表現に変換し、 bin2mat() によりバイナリ表現からマトリックス表現に変換できるので、既存コードにある初期値や出力用の関数はほぼそのまま使い回せる。

バイナリ表現化したことで盤面のほか候補についても64bitで表現できるようになったし、いっそのこと、あらかじめ8つのブロックの方向・反転・位置スライドの全パターンをメモリ上に展開しておくことにした。たとえばひとつのブロックの候補は以下のような196のuint64値で表現できる。

000000000000030e 000000000000061c 000000000000070c 0000000000000c07 0000000000000c38 0000000000000e03 0000000000000e18 000000000000180e 0000000000001870 0000000000001c06 0000000000001c30 000000000000301c 000000000000380c 0000000000003860 0000000000006038 0000000000007018 0000000000030e00 0000000000061c00 0000000000070c00 00000000000c0700 00000000000c3800 00000000000e0300 00000000000e1800 0000000000180e00 0000000000187000 00000000001c0600 00000000001c3000 0000000000301c00 0000000000380c00 0000000000386000 0000000000603800 0000000000701800 0000000001010302 0000000001030202 0000000002020301 0000000002020604 0000000002030101 0000000002060404 00000000030e0000 0000000004040602 0000000004040c08 0000000004060202 00000000040c0808 00000000061c0000 00000000070c0000 0000000008080c04 0000000008081810 00000000080c0404 0000000008181010 000000000c070000 000000000c380000 000000000e030000 000000000e180000 0000000010101808 0000000010103020 0000000010180808 0000000010302020 00000000180e0000 0000000018700000 000000001c060000 000000001c300000 0000000020203010 0000000020206040 0000000020301010 0000000020604040 00000000301c0000 00000000380c0000 0000000038600000 0000000040406020 0000000040602020 0000000060380000 0000000070180000 0000000101030200 0000000103020200 0000000202030100 0000000202060400 0000000203010100 0000000206040400 000000030e000000 0000000404060200 00000004040c0800 0000000406020200 000000040c080800 000000061c000000 000000070c000000 00000008080c0400 0000000808181000 000000080c040400 0000000818101000 0000000c07000000 0000000c38000000 0000000e03000000 0000000e18000000 0000001010180800 0000001010302000 0000001018080800 0000001030202000 000000180e000000 0000001870000000 0000001c06000000 0000001c30000000 0000002020301000 0000002020604000 0000002030101000 0000002060404000 000000301c000000 000000380c000000 0000003860000000 0000004040602000 0000004060202000 0000006038000000 0000007018000000 0000010103020000 0000010302020000 0000020203010000 0000020206040000 0000020301010000 0000020604040000 0000030e00000000 0000040406020000 000004040c080000 0000040602020000 0000040c08080000 0000061c00000000 0000070c00000000 000008080c040000 0000080818100000 0000080c04040000 0000081810100000 00000c0700000000 00000c3800000000 00000e0300000000 00000e1800000000 0000101018080000 0000101030200000 0000101808080000 0000103020200000 0000180e00000000 0000187000000000 00001c0600000000 00001c3000000000 0000202030100000 0000202060400000 0000203010100000 0000206040400000 0000301c00000000 0000380c00000000 0000386000000000 0000404060200000 0000406020200000 0000603800000000 0000701800000000 0001010302000000 0001030202000000 0002020301000000 0002020604000000 0002030101000000 0002060404000000 00030e0000000000 0004040602000000 0004040c08000000 0004060202000000 00040c0808000000 00061c0000000000 00070c0000000000 0008080c04000000 0008081810000000 00080c0404000000 0008181010000000 000c070000000000 000c380000000000 000e030000000000 000e180000000000 0010101808000000 0010103020000000 0010180808000000 0010302020000000 00180e0000000000 0018700000000000 001c060000000000 001c300000000000 0020203010000000 0020206040000000 0020301010000000 0020604040000000 00301c0000000000 00380c0000000000 0038600000000000 0040406020000000 0040602020000000 0060380000000000 0070180000000000

この値を bin2mat でデコードしてみるとブロックが見えてくる。

% python
Python 3.8.1 (default, Mar 12 2020, 17:27:26)
[Clang 11.0.0 (clang-1100.0.33.17)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import puzzle_a_day_solver
>>>
>>> puzzle_a_day_solver.bin2mat([0x000000000000030e])
array([[0, 1, 1, 1, 0, 0, 0],
       [1, 1, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0]], dtype=uint8)
>>> puzzle_a_day_solver.bin2mat([0x000000000000061c])
array([[0, 0, 1, 1, 1, 0, 0],
       [0, 1, 1, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0]], dtype=uint8)

8ブロック合計では、重複を除くと合計1196パターンあり、正味9568バイトのデータ量に収まるので、全てのパターンを予め展開しておいても、Core 2 DuoのプロセッサでももしかするとL1キャッシュに収まってしまうかもしれないデータ量だといえる(プロファイリングしていないので実際にどうなっているかは判らない)。

ブロックの衝突チェックは、従来方法では足し算をしていたが、今回は論理積(AND)を使用する。盤面 AND 候補を計算した結果、重複ビットがあるとゼロ以外の値になるので、論理積の結果がゼロ以外の候補は除外する。ここでも NumPy による vectorization を行う。

    blocks_f2_masked = blocks_f1_uint64 & mat_uint64
    blocks_f2_bool =blocks_f2_masked == 0
    blocks_f2_uint64 = blocks_f1_uint64[blocks_f2_bool]

特定セルを埋めてくれる候補かどうかを判断するためには、特定セルを示すビットが 1 である候補に絞り込めばよい。 mat2bin/bin2mat 向けに作った、各セルに対するビットを示すルックアップテーブルから 64bit のビットマスクを得て、先と同様にフィルタリングする。

    bit_pos = mat2bin_lut[pos[0], pos[1]]
    blocks_uint64_masked = blocks_uint64 & bit_pos
    blocks_f1_bool =blocks_uint64_masked != 0
    blocks_f1_uint64 = blocks_uint64[blocks_f1_bool]

基本的なアルゴリズムは変えずに内部表現だけ変更しているので、得られる結果は一緒だが、49秒かかっていた処理が3.5秒まで短縮できた。

単純な計算部分だけで考えればもっと速くなる(1秒は切れるだろう)と思っていたので、思ったより遅かった。



C言語で再実装してみた

翌週、実はC言語で再実装してみた

もうこれ以上は最適化なんてしないって思っていた。でも1秒を切れなかったのがやはり心残りだったんだと思う。

基本的なアルゴリズムは Python バージョンと一緒だが、本質的ではないところで 楽をしたり、異なる実装をしたりている。

まず Python バージョンでは盤面の制約やブロックの形状を配列として表現しておき、実行時に 64bit のバイナリ表現を得ていた。 C 言語でこれを書き直そうとするとちょっと面倒なので、 Python バージョンが得られたバイナリ表現をソースコード中にLUTとして埋め込みしておく。

ブロックのLUTと、ブロックのメタデータ(LUT内の開始位置と数量)を独立したデータとして持っている。各ブロックの大きさや形状の違いからブロック数量が異なる。このためLUT自体はひとつ一次元配列で持っているので、CPU L1キャッシュを無駄にしない。

現状のコードは日付の指定や結果の出力機能を持っていない。 Python バージョンと同じデータ構造なので、 Python モジュールとしてコンパイルしてしまい、 Python バージョンを宿主として足りない部分は既存コードを使い回そうかなと思っている。

C言語で書くと有り難いのが次に攻略すべきセルを選択する部分で、ここはどうしても Python 上で速くする方法を思いついていなかった。いくつかのパターンを試した感じでは NumPy に任せておいたほうが速かったので、そうなっていた。

# バイナリ化前
def next_cell(context):  mat = context['mat'] pos = np.unravel_index(np.argmin(mat), mat.shape) minval = mat[pos[0], pos[1]] if minval != 0: return None return pos
# バイナリ化後 def next_cell(mat):
mat = mat2bin_lut & mat pos = np.unravel_index(np.argmin(mat), mat.shape) minval = mat[pos[0], pos[1]] if minval != 0: return None return pos

この部分はC言語であれば素直に書ける。

/* 盤面 board に対して次のセルを選んで、その bit の値を返す */
inline uint64_t next_cell_bit(uint64_t board) {
    for (int y = 0 ; y < 7; y++)
        for (int x = 0 ;x < 7; x++) {
            uint64_t done = board & mat2bin_lut[y][x];
            if (! done)
                return mat2bin_lut[y][x];
        }
    return 0;
}

ある時点のC言語バージョンでは gcc の最適化なしで 40ms (0.04秒)、 -O3 で 20ms まで実行時間を短縮できる事を確認できた。M1 Macでは10msで完了したという報告ももらった(速っ!)。現時点のものは、もう少し最適化が進んでいる。


キャッシュミス分析

このソルバーは約10KBのLUTを使って、最大8回の再帰呼び出しするだけなので、この規模であれば、ここ10年のプロセッサーではCPUのL1 Cacheに載りきってしまうことが想像できる。以下は Ryzen 9 3900X の Linux box において cachegrind でこのソルバーをプロファイルしてみた結果である。

$ valgrind --tool=cachegrind ./solver
==114519== Cachegrind, a cache and branch-prediction profiler
==114519== Copyright (C) 2002-2017, and GNU GPL'd, by Nicholas Nethercote et al.
==114519== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==114519== Command: ./solver
==114519==
--114519-- warning: L3 cache found, using its data for the LL simulation.
50 solutions found
==114519==
==114519== I   refs:      100,596,976 .... 命令の参照数
==114519== I1  misses:          1,140 .... L1 キャッシュミス
==114519== LLi misses:          1,116 .... L3 キャッシュミス
==114519== I1  miss rate:        0.00%
==114519== LLi miss rate:        0.00%
==114519==
==114519== D   refs:       19,428,245  (18,233,828 rd   + 1,194,417 wr) .... データ読み書き数
==114519== D1  misses:          3,401  (     2,718 rd   +       683 wr) .... L1 キャッシュミス
==114519== LLd misses:          2,817  (     2,213 rd   +       604 wr) .... L3 キャッシュミス
==114519== D1  miss rate:         0.0% (       0.0%     +       0.1%  )
==114519== LLd miss rate:         0.0% (       0.0%     +       0.1%  )
==114519==
==114519== LL refs:             4,541  (     3,858 rd   +       683 wr)
==114519== LL misses:           3,933  (     3,329 rd   +       604 wr)
==114519== LL miss rate:          0.0% (       0.0%     +       0.1%  )

I1 miss rate および D1 miss rate が 0.0% となっていることで、プログラム自体もデータも L1 キャッシュに収まっていることがわかる。念のためソルバーの実行回数を増やしたものを同じくプロファイラにかけてみたりもしたが、大きくキャッシュミスが増えたり、キャッシュミス率が上昇したりする状況を確認できなかった。

LLd miss rate の 2213 rd は恐らく 64bit のキャッシュラインへの読み込みが2213回発生したということだと思うので、 2,213*8=17,704 [bytes] で、コード中で使っている LUT サイズが 10KB 前後、あとはヒープや自分が書いたものではない関数内のメモリ操作をあわせると、こんなものなんだなと思っている。

知識として CPU のキャッシュの事は知っていたけども、こういったデータを具体的に見る機会は今までなかったので、パズルついでにここまで楽しめるのはお得感があった。


これで終わりだと思うけど


一度「もうこれ以上はやらない」と書いていたのに色々と手を入れてしまったので、ほかにも思いついている最適化を試してしまうかもしれない。
  • mat2bin_lut の unroll
    試した範囲では認識できるほどの差がないことがわかっている
  • mat2bin_lut を引くのをやめて毎回計算で求める (のとどちらが速い?)
  • AVX512


おわりに

とりあえず数日間でソルバーを書いて遊んでみた内容をまとめてみた。

A Puzzle A Day のパズルはアナログでありながら、365日飽きもせずに遊べそうで、とても面白いと思う。同時に盤面は 7x7 未満とかなり小さく、私みたいに総当たりしてもそれほど難しくないので、プログラミング経験が浅くてもソルバーを実装にチャレンジするにはお手頃な問題ではないかと思う。


これまで使ってきた Mac を回想する

私が普段使いのコンピュータを Mac に変えたのは 2007 年のことだった。知人が悪名高き MacBook Air (初代で何もしなくてもCPUスロットルするようなひどい世代)を可愛がることに決めて、私に 2006 年モデルの白色プラスチックモデルの MacBook を譲ってくれたので、 Mac に乗り換えることにした。 CoreDuo, 4GB RAM とかの時代のモデルで、快適に使えていた気がする。後述の 2008 年モデル購入後に、さらに知人に引き取られていった。

時間軸としてはこちらのほうが前なのだが、もともと 2004年頃に G4 Mac を購入して持っていて、まあ16年以上前のことだから書いてしまってもいいかな。まだ所属会社のセキュリティポリシも緩かったので、会社への申請を通して自分の G4 Mac を会社のデスクに設置、社内ネットワークに接続して、いつもロードアベレージが高いメールサーバからメールを吸い上げて、 imapd を動かして最強のメールスプールとして使っていた。数年後には社内のセキュリティポリシの変化に伴い、社内にもっていた私物 PC (ほかに自作FreeBSD PCのIRCサーバなども置いていた)は撤収することになった。

新品で買った MacBook は 2008 年モデルの 13 インチで、この個体では FreeBSD のソースコード読み込んだり、勉強会などに参加したりでかなり使い込んだ。仕事用 Windows PC は Cygwin, xinetd などを組み合わせ、普段使いは gVim な環境になっていたが MacBook 上は普通に UNIX ですっきりした環境でよかった。今でも手元に残ってはいるけど、通電はほとんどしていない。

2011年、転職のタイミングで MacBook Air 13インチを購入してメインPCにした。外回りのセールスになって、会社からの支給コンピュータは MacBook 13 インチだったが、一日に 3 アポとか都内を走り回る業務スタイルにおいてあの重さのコンピュータを常に携帯するのは負担だったので、自分でコンピュータを持ち込んでいた。当時は国内に社員が3~4名しかいない会社でやり放題(?)していたが、いまだと許されないかもしれない。

翌年の MacBook Air 2012 13インチを買ったのは、上記 Air のハードウェア故障で修理に出している間にコンピュータがないのは困るということで、買い換えた。当時の Air はフルスペックでも20万しなかったし、ノート型コンピュータをとても酷使していたので、1年しか使ってなくても買い換えていいかなというぐらいの気持ちで買い換えた。 2011 年モデルと比べると内蔵グラフィックスの性能向上がすごくて、良いコンピュータだった。

この頃の Mac はリーマンショック後の円高の影響で、スペックの高い個体がかなり安く買えていたこともあって、エンジニアにとっての Mac は安くてコスパのいい使い捨てマシンだったという感じがあった。

退職後、 MacBook Pro 2014 15インチを購入。 Pre Type-C 世代としては2015年モデルが最強だったが、 2014年モデルもハードウェア、ソフトウェア的に非常がバランス取れていて良いコンピュータだった。IkaLogの開発に使用したのもこのコンピュータである。冷却機構に埃がたまりサーマルスロットリングの病気が発生、掃除が必要だったが、当初はそれぐらいのトラブルで、とても快適な個体だった。残念ながら、手元の個体はディスプレイやキーボードの破損などが度々発生し、維持しつづけても負債になると考えて、保証切れとともに手放すことにした。30万以上したが、15万円ぐらいで売れた。

2017年に現職に入った際、 MacBook Pro 2016インチをメインマシンにして、ここでは(いまごろ私が改めて言う話でもないが)バタフライキーボード等のデキが悪くて正直かなり使いづらいコンピュータになっていた。とはいえソフトウェア面での仕上がりは悪くなくて、 MS OneNote が同期に失敗しはじめると無限に CPU 時間を消費してとネットワークトラフィックを吐き続けることぐらいだったと思う。

なおこの MacBook Pro 2016 、 2019年の AppleCare 保証が切れ&リースアップ前にキーボードの保守交換(在庫の都合上UK->US)でめちゃくちゃ良いマシンになったと思う。酷評されていたバタフライキーボードも、改善版になってからはびっくりするほど入力しやすくなった。

キーボード交換の際、バッテリ交換、本体シャーシ交換、温まったときにクラック音が生じていた問題があり液晶パネル交換となり、システムボード以外は新品同様になったのでこのまま暫く使い続ける選択肢も考えたのだが、過去の経験上 Mac を修理なしで使い続けられるという感覚がなく、使い続けても故障のタイミングで想定外のキャッシュアウトを会社に負担させるのもどうかと思ったので、リースアップの際に泣く泣く手放した。

2019年、本当はノート型コンピュータなんて1台だけ持っていれば十分だと思っていたのだが、情シスなどと相談したうえで海外出張時の PC を普段使いと分けることになって、 MacBook Air 2019 を併用しはじめた。正直、あまり使っていないし思い入れのない個体。もっと使ってくれる人のところに行けたら、よかったのにね。のちにコロナウイルスの蔓延もあり、本当にほとんど出番がない。

いま在宅で普段使いしているコンピュータは MacBook Pro 2019 16インチで、キーボードのタイプ感がまた変化した。個人的には2016年の改善版のバタフライキーボードでもよかったかなと思うけど、まあ過去には戻れないので仕方がない。コロナウイルス禍にあり家から出ない日も増えたし、 MacBook Pro 2019 16インチは最強のリモートワーク母艦となっている。

ただ、この普段使い MacBook Pro 2019 、またOSのアップデートが増えてから、いまいちOSとして安定しなくなってきた。ハードウェアとしては気に入っているんだけども、ソフトウェアとのバランスが微妙になったのかなーと感じている。

「インストールしているソフトウェアや接続しているハードウェアが悪いんじゃないか」「俺のMacは暴れねえよ」などとは度々言われるのだが、なぜかうちの Mac はどうしても暴れてしまう。ここ1年ぐらいで kernel_task の CPU 時間消費が極端になってきて実用に耐えないレベルになりつつあるので、仕事する上で困るし、対策を打たないといけない。

自分にとっていちばん Mac が使いやすかったのは、 2012年~2015年のことだった。2017年以降、新しい Mac を手にする際には毎回「これが自分にとって最後の Mac になるかもしれない」と思っている。

2021年4月10日土曜日

高リフレッシュレート対応4K液晶ディスプレイ ASUS ROG XG27UQ を購入した

 高リフレッシュレートなディスプレイに買い換えようと思って以来半年近くたち、ようやく本命のディスプレイが手元に届きました。



今回のXG27UQは2021年2月に国内向けに発表されたモデルで、これまで秋葉原などでお店を回っても実物を見かけることはありませんでした。発表当初にすぐ予約された方は2月中に入手できたようですが、4月に入ってようやく実物が届いたぐらいで、現時点で欲しくても実物を見られる方は限られていると思います。このモデルは実売で10万円近くしますし、「失敗したくないので少しでも多く情報が欲しい」という方もいらっしゃるかと思います。このため、所感をまとめておくことにしました。

調べてみると、メーカーからテスト機を借り受けたブロガー等がすでにレビュー記事を投稿されていますし、そういった方でカバーされている分については、そういった記事にお任せすることにしました。私の記事では、他の記事ではあまり触れられていない部分について触れていこうと思います。


ファースト・インプレッション編

マニュアル冊子が付属していない

本製品は付属品として製品保証についての冊子、1枚っきりのクイックスタートガイド、およびキャリブレーションレポートが付属していますが、マニュアルは同梱されていません。スタンド部分を外す方法がわからずに困っていたところ、 ASUS のサイトにはマニュアルが PDF で存在していることがわかりました。

https://dlcdnets.asus.com/pub/ASUS/LCD%20Monitors/XG27UQ/XG27UQ_Japanese.pdf

マニュアル冊子なんて一度使い始めたらほとんど見返すこともないのは事実ですし、意図的に省略されているのでしょう。とはいえ、 10 万円近いモニタですし、今回の製品はマニュアルを見ないとよく判らない機能やギミックも積まれているモデルです。紙媒体でマニュアルが付属されていたり、もしくは少なくともURLや検索キーワード、QRコード等でもよいので、マニュアルへの案内があると良かったなと思いました。


日常の利用編

複数ソースの切り替えが面倒。ファームウェア更新による改善を期待

XG27UQ は DisplayPort 2入力、 HDMI 2入力で合計4入力利用できる点がひとつの特長です。ディスプレイです。しかし、ディスプレイの入力を切り替えるためには画面裏側右手の赤いスティックを使い、クリック→下→下→下→右と操作し、その上で入力ソースをスティックで選択する流れになっており、煩雑です。

赤いスティックの下にはゲーミングモードを設定する画面へのショートカットがふたつあります。これらのボタンで、GamePlus設定画面、およびGameVisual設定画面への直接遷移できるようになっていますが、たぶん、私は、どちらもほとんど押す機会がないでしょう。これらのボタンから入力ソースの切り替え画面へ遷移できるような設定が可能となるファームウェアアップデートに期待したいです。複数の入力ソースを接続する方の多くは、同じような感想をお持ちになるのではないでしょうか。


USB3.0ハブ機能は、ディスプレイの主電源と連動/非連動が選べる

XG27UQ は USB3.0 の2ポートUSBハブ機能を搭載しています。私の場合、ダウンストリームには、ディスプレイの付近にあるデバイスとして、Webカメラとして利用している一眼デジタルカメラ(Canon EOS Kiss X6i)とアイトラッカー(Tobii Eye Tracker 5)を接続しています。ディスプレイ自体にこの機能を求めてはいないのですが、セットアップがすっきりした点についてはメリットを感じました。


このUSBハブ機能はディスプレイ機能と独立して動きますが、ディスプレイの主電源がオンの状態でのみUSBハブが動作する連動設定と、ディスプレイの主電源の状態にかかわらず外部電源が供給されていればUSBハブが動作する非連動設定のどちらかを選ぶことができます。

工場出荷時は主電源と連動する設定になっていますが、私の場合で常時通電のデスクトップPCとの組み合わせで利用するため、USBハブが常時動作する設定に切り替えました。


ディスプレイアームとの組み合わせ利用について

XG27UQ はディスプレイアームへの取り付けに対応しています。ただし、アームの取り付け時に標準スタンドの取り外し方がすぐに判からず、マニュアルを見ながら試行錯誤したほか、この機種特有の考慮点があるので、ここで紹介したいと思います。



標準スタンドの取り外し方

この作業には、化粧パーツの取り外しにマイナスドライバー、M4ネジを付け外しするためのプラスドライバーが必要です。

工場出荷時にはスタンド用の足が取り付けられた状態になっています。足のまわりにある半リング形状の化粧パーツを取り外します。スタンドの裏を覗き込むとマイナスドライバーを差し込める隙間があるので、ここにマイナスドライバーを差し込んで化粧パーツを引き上げます。

パーツが浮いてきたら、半リング形状の化粧パーツ2点を、ディスプレイ本体から平行に離すように取り外します。取り外し時に多少力をかける必要がありますが、樹脂パーツ自体は十分な強度があるので、丁寧に外せば問題ありません。この作業を終えると、VESA規格のM4ネジが4本露出します。

足のまわりに見えてきたVESA規格のM4ネジを4本はずすと、標準スタンド用の足がはずれて、ディスプレイアームを取り付け可能な状態となります。

半リング形状の化粧パーツは取り外したスタンドに取り付けられるので、保管時にはスタンドにはめて保管しておくとよいでしょう。


VESAマウントのネジ穴は25mm の窪みの中にある

ディスプレイアームの種類によっては、カメラのクイックシューのように、あらかじめディスプレイ側に小さな部品を取り付けておいて、設置済みのディスプレイアームに固定できるような機能をもった物があります。このような場合VESA標準のネジ穴のまわりに十分なクリアランスが必要です。また、スタンドを非純正品に交換した場合にも注意が必要なポイントでしょう。

今回は colebrook bosson saunders 製の Wishbone ディスプレイアームに取り付けるつもりでいたので、この部分は気になっていましたが、結果的には十分なクリアランスがあり、Wishbone アームに対して、問題なく載せたり外したりできることが確認できました。 


ディスプレイアーム利用時、ビデオ用ケーブルを完全に隠せない

XG27UQ は下側から DisplayPort/HDMI などのケーブルを差し込みます。標準スタンドを利用する場合にはあまり気にならないでしょうが、ディスプレイアームに載せる場合は、ビデオ用のケーブルが正面から見えてしまう可能性があります。

がんばって隠すことも不可能ではないのですが XG27UQ は DisplayPort 1.4 に対応した 4K 144Hz 対応のディスプレイで、これを利用する場合には DisplayPort 1.4 に対応した比較的太いケーブルを使用することになるのではないでしょうか。

しかし、上向きに刺さった太いケーブルをディスプレイの裏側で片付けるだけの十分なスペースがないため、正面から見たときには、ビデオ用のケーブルはディスプレイの下側に少し見えるぐらいのセッティングに落ち着くかと思います。もちろん気合いで見えないように隠してもよいでしょうが、アームを動かしたときにケーブルやコネクタに負担がかからないようにある程度の遊びも必要ですし、この点は諦めることにしました。


その他編

当然ながら 4K 144Hz には高品質なケーブルが必要

これまで、2012年に購入した 7m の DisplayPort 1.2ケーブルでPCとディスプレイを接続し、4K 60fpsで動作させていました。このケーブルを利用していたのは諸事情により「手元で余っていた」というのが最大の理由です。(今でも未使用の新品が1本手元にあります...)

このケーブルでも 4K 144Hz はいちおう映ったのですが、不定期に画面がブラックアウトする現象が発生しました。恐らくケーブルの品質的に映像信号が時々乱れているのだと想像できます。

FullHD 144Hz に対して 4K 144Hz は時間あたりに表示するピクセル数が4倍になります。このためビデオケーブルの中を流れる信号の速度が上がっています。 Wikipedia の DisplayPort ページで調べてみたところ、 4K 144Hz は DisplayPort 1.4 仕様からの仕様で、ケーブルの中を 25.92Gbps の信号が流れているようです。 1.2 の時代は 17.28Gbps だったので、データの転送量が1.5倍になっていて、恐らくそれだけDisplayPortケーブル内のビットクロックも上がっているようです。

ディスプレイに付属する DisplayPort 1.4 ケーブルを利用することも考えましたが、手元では昇降デスクやディスプレイアームを利用しており、 3m 程度のケーブル長を必要としていたので、 3m の DisplayPort 1.4 対応ケーブルを購入して交換しました。

また、ビデオカードの DisplayPort コネクタの片方が緩いようで、本体への衝撃ですぐブラックアウトしてしまう事があったので、もう片方の DisplayPort コネクタに装着して安定を確認しました(ビデオカードのメーカー保証で交換依頼をしてもいいかもしれませんが、手間を考えるとこの対応でいいかなぁと思っています)。


MacBook Pro 16インチ (2019) から HDMI で 4K 60Hz で安定出力できている

MacBook Pro から 4K 解像度で出力する際になかなか安定しないイメージを持っていましたが、XG27UQ では HDMI ケーブルを接続するだけで 4K 60Hz で出力された点が拍子抜けでした。ここ一週間ほど、ノートラブルで動作しています。

LG 社のディスプレイでは 4K 60Hz を受け付けるためには追加の設定(DeepColor)が必要だったりして、この設定を行うと映る時と映らない時があるなどしてストレスを感じたので DisplayPort 接続による 4K 60Hz もしくは HDMI 接続による 4K 60Hz を使い分けていました。

不都合が感じたら DisplayPort での 4K 60Hz に切り替えることを考えるでしょうが、実用上問題を感じないうちは、試しに HDMI の 4K 60Hz で使ってみようかと思います。


まとめ

XG27UQ は、4系統入力の4K解像度・高リフレッシュレートディスプレイとしては期待通りの仕上がりだと感じています。

一点だけ不便な点を挙げるとすれば、入力系統の切り替えに必要な操作数が多いことです。この部分は4系統入力を魅力に感じて購入するユーザーにとっては非常に重要なポイントです。もしエンドユーザ側でファームウェアアップデートが可能な仕組みが用意されているのなら、後からでも改善できる点ですから、ASUSには是非検討を御願いしたいところです。

これまで液晶ディスプレイといえばシャープ、LGなど自社で液晶パネル技術を製造できるメーカーの製品を利用していました。今回のASUS ROG XG27UQは実売価格で10万円近くするモデルで、下手な4Kディスプレイの2倍以上の価格です。ASUS自体は液晶パネルを作れるわけではないので買ってきている(というか製品規格だけで、他メーカーに仕様を指定して生産させている可能性も高い)メーカーですので、正直に言えば、そういったメーカーの製品を選定すること自体に抵抗もありました。最初の一週間から「買わなければ良かった」みたいな悪い印象にもならず、ホッとしています。

To Be Continued

フォトトランジスタを使って応答速度などをの特性を測定しているため、結果がまとまったら続編としてまとめたいと思います。

2021年4月8日木曜日

Radeon RX 6800 XT の OpenCL を有効化する

Radeon RX 6800 XT で OpenCL プログラムを動かそうとすると、OpenCL プラットフォームとして同 GPU が列挙されてこなかったので、調べたら、レジストリをちょっと弄る必要があるっぽい。どうやら OpenCL プログラムはこのキーから OpenCL プラットフォームの実装を見つけてるようだ。


Radeon のドライバをインストールもしくはアップデートしたタイミングで、以下のようなディレクトリ、ファイルができる。

C:\Windows\System32\DriverStore\FileRepository\*.inf_amd64_*\amdocl64.dll


amdocl64.dll のフルパスが確認できたら、 regedit.exe を起動して、 コンピューター\HKEY_LOCAL_MACHINES\SOFTWARE\Khronos\OpenCL\vendors に、以下のキーを作成する。

  • 名前: 上記 amdocl64.dll のフルパス
  • 種類: REG_DWORD
  • データ: 0x00000000 (0)
このキーを作成した後に OpenCL を利用するプログラムを実行すると、 Radeon GPU が OpenCL デバイスとして認識される。もし認識されない場合は amdocl64.dll へのパスがおかしいとか、過去のドライババージョンの amdocl64.dll へのパスになっていないかを確認するとよさそうだ。

手元で Radeon のドライバを更新するたびにコレでひっかかってる気がするが、どうしてドライバのインストール時に自動的にやってくれないのかねえ。何も見ずに何すればいいか思い出せるほどの頻度でやることではないが単純作業ではあるので、いっそのことツールなど書いて自動化すると幸せかもしれない。。。