I’ve been gradually working on an AI for “5×5 Shogi,” a subset of standard Shogi. Here are some notes on what I’ve learned.

Data Structure

Each piece is managed using bitboards. For example, if a Black pawn exists at position 7, it’s represented as bitboard[B_PAWN] = 0x40. The range of rooks and bishops is derived using AVX2’s _pext_u32 instruction [5].

Search Strategy

The basic approach uses alpha-beta pruning for search. Additionally, legal moves are sorted while performing iterative deepening. When the same position appears, a transposition table is used to narrow the alpha-beta window. I tried Null-Window (PVS) search, but it didn’t become significantly faster. Sometimes it’s even slower. The sorting method is probably inadequate.

Evaluation Function

Currently using a simple material evaluation based only on piece values. Improvements are essential.

USI (Universal Shogi Interface) Protocol

USI is one of the protocols for connecting Shogi GUI software [8] with AI engines [6,7]. The AI receives positions and time controls from the GUI software and returns the chosen move. I’ve implemented basic support for it.

Parallelization with OpenMP

The search is parallelized using OpenMP. Legal moves from a given position are searched in parallel. I wanted to link statically as much as possible, so I investigated a bit.

  • visual c++
    • Configuration Properties - C/C++ - Language - OpenMP Support: set to “Yes”
    • Configuration Properties - C/C++ - Code Generation - Runtime Library: set to “Multi-threaded (/MT)”
    • Depends on VCOMP{90,100,110,120}.dll
    • VCOMP{90,100,110,120}.dll is dynamically linked even with /MT, so I might try using a redistributed version [1,2].
  • gcc
    • Depends on libgomp, but there seems to be a way to link it statically [4].
  • intel compiler
    • Apparently libiomp5m.lib can be statically linked [2].
    • Static linking is discouraged, but the -openmp-link static option should work (icpc -openmp -openmp-link static hello.cpp) [3].

References