六目並べハードウェアデザインコンテストへの挑戦

摘要

本稿では、FPGAデザインコンテストのために開発した六目並べハードウェアソルバーNexus6-mk3について、そのアルゴリズム、アーキテクチャ、実装と性能を解説する。このソルバーは、本研究で提案する探索候補の2段階生成手法にアルファベータ枝刈り法を組み合わせたmini-Max深さ優先探索により、探索時間を大幅に削減している。評価関数の計算や探索候補である子ノード生成の細粒度並列性を活用するハードウェアアクセラレータにより、110MHz動作のNIOS IIプロセッサおよび2.93GHz動作のCorei7プロセッサ単一コアに対し、それぞれ約8万倍と640倍の速度向上が達成された。使用したFPGAボードは安価で消費電力が低く、コスト性能比や電力性能比の点でも、FPGAによるソルバーはソフトウェア実装と比べて非常に優れた実現方法であることが示された。