AIエンジン開発チームの研修課題を公開！ "n-queens 問題"

近藤憲児

2022年12月15日 09:30

はじめまして、株式会社スカイディスクの近藤です。 最適ワークス というサービスの AI の部分を作っている AIエンジン開発チーム のマネージャーをしています。

最適ワークスの魅力の一つに「 AI によるスケジュールの立案」があります。熟練の工程マンの方が日々様々な制約を考慮しながら立てている工程スケジュールを、最適ワークスの AI が素早く立案し、利用者に提案する、というものです。

AIエンジン開発チームでは、このスケジュールの立案する AI のアルゴリズムの設計や実装を行っています。まあ、やっていることはそれだけではないのですが。

今回は、そんなAIエンジン開発チームの研修課題: n-queens 問題 をご紹介します。

Tech 系企業の開発チームが時折公開する研修資料には、そのチームが重んじるスキルが象徴されていますよね。

これはそれに倣った、私達のチームの自己紹介です。

研修課題

以下の論文を参考にして、 n = 1,000,000 とした n-queens 問題の解の1つを 200 秒以内に見つけるプログラムを、 Python で実装してください。https://aaai.org/Papers/AAAI/1990/AAAI90-003.pdf

早速ですが、この課題の文中にある n-queens 問題についてご説明しましょう。

n-queens 問題

n-queens の queen とは、チェスのクイーンの駒のことです。

チェスのルールはご存知ですか？私は知りません。そんな私でもこの問題は理解できるので、チェスのルールを知らなくても大丈夫です。

n-queens の頭の n には具体的な数字が入ります。まずは簡単のために、 n=8 とした 8-queens 問題について説明します。 Wikipedia の記事も参考にしてください。

クイーンの駒は、以下のように上下左右斜めの方向ならば、どこでも動けます。

さて、 8×8 マスのチェス盤に 8 個のクイーンを配置することを考えます。ただし、どのクイーンのペアに注目しても、クイーンが互いにぶつからないように配置せねばなりません。

例えば、クイーンを以下のように配置すると、ぶつかるクイーンのペアが存在しますね。これはだめです。

以下はどうでしょうか。どのクイーンを見ても、他のクイーンとぶつかることがありません。したがって、以下は解の一つです。

このような理想的な配置を求めることが、 8-queens 問題です。

ちなみに 8-queens 問題の解は複数あります。 Wikipedia を覗いてみてください。

ここでこの 8 を再び n に置き換えるだけで、 8-queens 問題は n-queens 問題へと自然に拡張できますね。つまり、 n-queens 問題は以下のような問題です。

n×n マスのチェス盤に n 個のクイーンを配置することを考えます。ただし、どのクイーンのペアに注目しても、クイーンが互いにぶつからないように配置しなけばなりません。そのような配置を見つけてください。

そして私達の研修課題は、n=1,000,000 としたときの n-queens 問題の解を一つ見つけることです。

「この課題、なにが難しい？」

ひょっとしたら、次のように考える方もいらっしゃるかもしれません:

「コンピュータを使っていいんだよね？ならばしらみつぶしにクイーンを配置してみて、愚直に一つ一つ確かめてみれば、いつか見つけられるでしょ。簡単じゃないか」

興味深いことに、それは不可能です。

どういうことか。まずしらみつぶしに確かめるクイーンの配置が、そもそも何パターンあるかを考えます。

n×n マスのチェス盤に n 個のクイーンを配置するときの配置パターンの数は「 n×n 個のそれぞれ異なる数字が書かれたボールから n 個を選ぶとき、ボールの組み合わせは全部で何通りあるか？」という問題に置き換えられるので、答えは $${ {}_{n^2} \mathrm{C}_n }$$ パターンです。

このままだとよくわからないので、ざっくり近い数に置き換えて $${ n^n }$$ パターンとして考えます。

それでは n=1,000,000 のときを考えます。このときクイーンの配置パターンの総数は $${ 1,000,000^{1,000,000} }$$, つまり 10の600万乗 なわけです。

10の600乗が
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 なので、 10の600万乗は、これをあと 1 万回コピペしてようやく表現できます。

ここで、コンピュータが1秒間で処理できるパターン数をだいたい 10の9乗であるとして、宇宙のはじまりからこれまでの時間を 137億年=およそ10の18乗秒とするならば、仮に宇宙が誕生してこれまでの時間ずっと計算を続けていたとしても、たかだか 10の27乗 パターンしか確かめられません。

この調子だと 10の600万乗すべてをしらみつぶしに調べようと思ったら、少なく見積もっても、宇宙誕生から今までを、あと 10の500万乗回は経験しなければなりません。ちなみに 10 の 27乗をちゃんと表現すると 1000000000000000000000000000 ですね。宇宙誕生から今までこれっぽっちしか計算できないんですね。つまり、しらみつぶし作戦は到底不可能です。

ところで、私達の研修課題は、これを 200秒以内 に終わらせることです。

つまり、ここにはやはりテクニックが必要です。

「何が面白いの？」

私が大学院で数学の研究をしていた時から、私が実家に帰省して研究内容を母に話すと、母は怪訝な顔をしながらこの質問をしてきます。今でもそうです。

クイーンを上手に並べることそのものには端的に意味はありません。ここで興味があるのは、その背後にある理論です。

驚くべきことに、この問題を解く手法をそのまま利用して、数独パズルを一瞬で解いてしまうプログラムを書くこともできます。また東野圭吾の『容疑者Xの献身』でも触れられた「四色問題」という有名な数学の問題にも関わりがあります。そして何より、最適ワークスでスケジュールを立案することにも使われています。

この理論はいわゆる 組合わせ最適化 と呼ばれる領域に属するものです。 AI というワードから真っ先に連想される "ディープラーニング" や "機械学習" とは一応は区別されますが、これらとは不可分な関係であり、そして組合せ最適化にもまた学問的に豊饒な世界が広がっています。

このあたり、また別の機会に深堀ってお話したいなと思ってます。

以上が、私達の研修課題 "n-queens 問題" でした。

こういう面白いことを考えながら、日々楽しく開発をやっています。

以下、脚注:

ざっくり計算の仕方: $${ {}_{n^2} \mathrm{C}_n }$$ の分母は Stirling の近似式を用いて $${ O(n^n) }$$ に、分子は全てを $${ O(n^{2n}) }$$ に置き換えれば、全体的に $${ O(n^n) }$$ として考えられる。
ちなみに n-queens 問題の解を $${ O(1) }$$ で求められる方法は存在して、こちらの論文に書いてある。ただこの記事の主題はそこではないので、これは参考まで。

スカイディスクは積極採用中！！

スカイディスクは、事業拡大に伴い絶賛採用強化中です。また、上場を見据え、バックオフィスの募集も積極的に行っています。成長ベンチャーで働きたい、上場を経験したいと思っている方は、是非下記URLから募集要項を確認してください。

AI エンジニアはこちらから！

この記事が気に入ったらサポートをしてみませんか？