Trax Solver on Zynq using incremental update algorithm

Hiroshi Nakahara; Tetsui Ohkubo; Hideki Shimura; Ryotaro Sakai; Chiharu Tsuruta; Takahiro Kaneda; Hideharu Amano

doi:10.1109/FPT.2016.7929564

Trax Solver on Zynq using incremental update algorithm

Hiroshi Nakahara, Tetsui Ohkubo, Hideki Shimura, Ryotaro Sakai, Chiharu Tsuruta, Takahiro Kaneda, Hideharu Amano

Department of Information and Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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.

Original language	English
Title of host publication	Proceedings of the 2016 International Conference on Field-Programmable Technology, FPT 2016
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	323-326
Number of pages	4
ISBN (Electronic)	9781509056026
DOIs	https://doi.org/10.1109/FPT.2016.7929564
Publication status	Published - 2017 May 15
Event	15th International Conference on Field-Programmable Technology, FPT 2016 - Xi'an, China Duration: 2016 Dec 7 → 2016 Dec 9

Other

Other	15th International Conference on Field-Programmable Technology, FPT 2016
Country/Territory	China
City	Xi'an
Period	16/12/7 → 16/12/9

ASJC Scopus subject areas

Computer Networks and Communications
Electrical and Electronic Engineering
Safety, Risk, Reliability and Quality
Instrumentation
Hardware and Architecture

Access to Document

10.1109/FPT.2016.7929564

Cite this

Nakahara, H., Ohkubo, T., Shimura, H., Sakai, R., Tsuruta, C., Kaneda, T., & Amano, H. (2017). Trax Solver on Zynq using incremental update algorithm. In Proceedings of the 2016 International Conference on Field-Programmable Technology, FPT 2016 (pp. 323-326). Article 7929564 Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/FPT.2016.7929564

Trax Solver on Zynq using incremental update algorithm. / Nakahara, Hiroshi; Ohkubo, Tetsui; Shimura, Hideki et al.
Proceedings of the 2016 International Conference on Field-Programmable Technology, FPT 2016. Institute of Electrical and Electronics Engineers Inc., 2017. p. 323-326 7929564.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Nakahara, H, Ohkubo, T, Shimura, H, Sakai, R, Tsuruta, C, Kaneda, T & Amano, H 2017, Trax Solver on Zynq using incremental update algorithm. in Proceedings of the 2016 International Conference on Field-Programmable Technology, FPT 2016., 7929564, Institute of Electrical and Electronics Engineers Inc., pp. 323-326, 15th International Conference on Field-Programmable Technology, FPT 2016, Xi'an, China, 16/12/7. https://doi.org/10.1109/FPT.2016.7929564

@inproceedings{9c04c1fb511c4c7aa8f0bff19f609f16,

title = "Trax Solver on Zynq using incremental update algorithm",

abstract = "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.",

author = "Hiroshi Nakahara and Tetsui Ohkubo and Hideki Shimura and Ryotaro Sakai and Chiharu Tsuruta and Takahiro Kaneda and Hideharu Amano",

year = "2017",

month = may,

day = "15",

doi = "10.1109/FPT.2016.7929564",

language = "English",

pages = "323--326",

booktitle = "Proceedings of the 2016 International Conference on Field-Programmable Technology, FPT 2016",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

note = "15th International Conference on Field-Programmable Technology, FPT 2016 ; Conference date: 07-12-2016 Through 09-12-2016",

}

TY - GEN

T1 - Trax Solver on Zynq using incremental update algorithm

AU - Nakahara, Hiroshi

AU - Ohkubo, Tetsui

AU - Shimura, Hideki

AU - Sakai, Ryotaro

AU - Tsuruta, Chiharu

AU - Kaneda, Takahiro

AU - Amano, Hideharu

PY - 2017/5/15

Y1 - 2017/5/15

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85021397422&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85021397422&partnerID=8YFLogxK

U2 - 10.1109/FPT.2016.7929564

DO - 10.1109/FPT.2016.7929564

M3 - Conference contribution

AN - SCOPUS:85021397422

SP - 323

EP - 326

BT - Proceedings of the 2016 International Conference on Field-Programmable Technology, FPT 2016

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 15th International Conference on Field-Programmable Technology, FPT 2016

Y2 - 7 December 2016 through 9 December 2016

ER -

Trax Solver on Zynq using incremental update algorithm

Abstract

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this