数独・ナンプレを画像から解く AI を作る

本記事は DeNA 23 新卒 Advent Calendar 2022 の 12 日目の記事です．

11 日目の記事は @bigbell さんによる『プライベートIPしか振られていない環境でサーバを外部公開するための個人的ベストプラクティス』という記事でした．ぜひご覧ください！

DeNA 公式 Twitter アカウント @DeNAxTech では Blog 記事だけでなくいろいろな勉強会での登壇資料も発信してますので，ぜひフォローして下さい！

こんにちは．DeNA 23 卒内定者の @a5chin です．
大学では情報工学を専攻しており，医学ドメインの研究をしています．
今回は，PythonやAIに興味を持っている人たちの刺激になればと思い記事を書いてみました．

1. はじめに

Pythonを使ってナンプレ・数独の画像から自動で解答を導き出す AI (人工知能) を作ったので記事にします．
概要としては，PyTorchで作成したCNN¹を用いて画像認識をさせて文字を獲得したのちに深さ優先探索（DFS）²を行っています．

下記にてソースコードを公開しているのでぜひ見ていってください！
Star や PR を頂けるとやる気やモチベーションが上がります↓

2. 成果物

下記の様にナンプレ・数独の写真から一瞬で答えを導き出せます．

上記の画像をクリックすると実行している様子を再生できます

3. 背景

ある週末に，家族で新聞のナンプレ・数独を解いていた時のことです．
どれだけ時間をかけてもあまり空白が埋まらず，解けない問題がありました．

そこで，どうせ解くことができないのなら，今自分が学んでいる AI を使って数独・ナンプレを自動で解いてしまおうと考えました．

4. アルゴリズム

現状では

1. AI による文字認識
2. 獲得した文字をもとに深さ優先探索（DFS）²をかける

といった 2 段階のアルゴリズムとなっています．
特に AI による文字認識に関しては精度 100% の必要があるため，難しいタスクです．

下記にフローチャートを用意したので，参考になれば幸いです．

将来的に手書き文字の問題も解きたいと考えているため OCR は不採用となりました

4.1. 改善点

現状で考えられる改善点として 2 点考えられるのでそれぞれ紹介します．

4.1.1. 計算時間

現状の解法である深さ優先探索（DFS）²では，計算量は $O(n^3)$ で体感スピードは特に問題ありませんでしたが，線形計画法³を用いると $O(n^2)$ で計算でき，より高速に解答を導けるという話を聞いたので，改善出来次第更新していこうと考えています．

4.1.2. 誤り訂正

文字認識タスクにおいて，特定条件で精度 100% を満たしているものの，必ずしも達成できるものではありません．
そこで，文字を間違えて認識してしまった際に考えられる方法の 1 つとして誤り訂正が考えられます．
この誤り訂正についても改善出来次第更新していきます．

5. 苦労した点

苦労した点は大きく分けて 3 点あるのでそれぞれ紹介しようと思います．

5.1. 自作データセットの作成

一般的にAI（人工知能）は，膨大なデータ（データセット）を勉強させることで精度が上昇します．

数字のデータセットで検索をかけても MNIST データセット⁴しか引っかかりませんでした．
そこで，この MNIST データセット⁴を使って学習及び推論してみた結果，文字認識の精度が 70% 程度と目標である 100% とは程遠い結果になってしまいました．

実際に推論する数字の画像は以下の様な手書きではないデジタルな文字のため，データセットを自作する必要があると考えました．

そこで上記の様な，空白, 1, 2, 3, 4, 5, 6, 7, 8, 9 の 10 種類の画像をとりあえずそれぞれ 10 枚ずつ収集しました．
この自作のデータセットを使用して学習及び推論を行った結果，精度が 90% と目標の 100% まであと一歩というところまできました．
精度がかなり上昇したという事はデータセットが大きな問題だったのですね！

データ数が少ないため torchvision の transforms を使用して学習に使用する画像を変形させています

5.2. 空白と 1 の識別

2 つ目の苦難は，意外にも空白と 1 の識別です．
というのも，正答率が 100% でなかったので，推論結果と正解を比較してみたところ，空白であるべきマスが 1 と推測されていたからです．

一体なぜなのか．考えた結果，4 辺の黒線が悪さをしているのではないかという結論に至りました．
CNN¹の特性上，横隅の黒い直線が 1 と識別されているのではないかという理由からです．

その真偽を確かめて精度を上昇させるために，プログラムの中にランダムでマスの 4 辺に黒線を描き込むデータオーギュメンテーション⁵を実装させました．

その結果，精度を 98% まで上昇させることができました！
つまり，4 辺の黒線が悪さをしているのではないかという仮説は正しかったということになりますね！
あと少しです！

5.2. 精度 100% の実現

ナンプレ・数独を正しく解き切るには数字の認識率 100% は必要不可欠です．
そこでImageNet⁶で事前学習済みの重みを使用し，かつ学習率⁷を工夫しました．ちなみに本記事ではResNet18⁸を用いています．

学習率には timm のCosineLRSchedulerを使用しており，以下の様な概形をしています↓

事前学習した特徴量を有効利用するため，この様な学習率⁷（WarmUp）を選択しました．
そのために，初期の学習率⁷を 0 に近い値としています．

その結果，精度 100% を達成できました！

6. おわりに

今回は，私が作成したナンプレ・数独を解くことのできる AI についての記事を書きました．
いくつか解決に苦労したタスクがありましたが，なんとか形になったので一安心です！

13 日目は @YusukeTagawa さんによる『PlaywrightによるE2E自動テスト入門』という記事が公開されるのでお楽しみに！！

1. Convolutional Neural Network （畳み込みニューラルネットワーク）は，畳み込み層とプーリング層をもつニューラルネットワークで，画像から特徴量を抽出するために効果的なモデルです． ↩ ↩²

2. バックトラック法や縦型探索とも呼ばれ，木やグラフを探索するためのアルゴリズムです．人間が迷路を解く時などに使用します． ↩ ↩² ↩³

3. 線形計画法（Linear Programming）とは，数理計画法において，いくつかの 1 次不等式および 1 次等式を満たす変数の値の中で，ある 1 次式を最大化または最小化する値を求める方法を指します．線形計画法の対象となる最適化問題を線型計画問題といいます． ↩

4. さまざまな画像処理システムの学習に広く使用される手書き数字画像の大規模なデータベースのことで，米国商務省配下の研究所が構築したこのデータベースは，機械学習分野での学習や評価に広く用いられています． ↩ ↩²

5. Data Augumentation（データ拡張)とは，学習データ(訓練データ)の画像に対して平行移動，拡大縮小，回転，ノイズの付与などの処理を加えることで，データ数を人為的に水増しするテクニックです．学習データが少ない時に非常に有効な手法です． ↩

6. 物体認識ソフトウェアの研究で用いるために設計された大規模な画像データベースのことで，400 万を超える画像に手作業でアノテーションを行い，画像にどのような物体が写っているかを示しています．また，100 万枚以上の画像にバウンディングボックスも付与されています． ↩

7. 機械学習の最適化において，重みやバイアスなどのパラメータを 1 度にどの程度変化させるかを表すハイパーパラメータのことを指します． ↩ ↩² ↩³

8. 2015 年に発表された深さが 18 層の代表的な CNN モデルです．何層かの畳み込み層と Shortcut Connection から成る Residual Block をとりえれることで ILSVRC で優勝している ResNet 系統のモデルです． ↩