Trax solver on Zynq using incremental update algorithm
Hiroshi Nakahara, Tetsui Ohkubo, Hideki Shimura, Ryotaro Sakai, Chiharu Tsuruta, Takahiro Kaneda, Hideharu Amano · 2016
This paper proposes a software/hardware co-design system for a Trax solver. Since development with Hardware Description Language (HDL) is tough work, we selected an approach: 1.writing C++ code, 2.finding bottleneck of the problem, and 3. re-writing the bottleneck part in the High Level Synthesis (HLS). Generally, game AI algorithm is divided into 3 parts, data structure, searching, and board evaluation. In this design, we focused on the data structure and implemented an incremental update algorithm. As a result, we can detect a line and an attack with O(1). Also, we implemented a local pruning, which reduces search area when the search depth becomes large in alpha beta tree search. The implemented solver works with 150MHz clock on Xilinx XC7Z020-CLG484 of Digilent ZedBoard.