Shogi AI Past, Present, and Future

As always, opinions are my own, not those of Lichess.org. My transcript relies upon Google Translate plus my own knowledge.

Introduction and Past Era (1974 - 2012)

• Evaluate of a shogi position (for example +1 per piece, +100000 for checkmate) using minimax search
  • 4-fold repetition (including pieces in hand) is considered sennichite (draw)
  • Bonuses for active pieces, for example a bishop on a long open diagonal
  • In the start position, there are 30 legal moves; however on average there are about 80 legal moves!
• Automated parameter tuning using stochastic gradient descent (SGD)
• Search optimizations (alpha-beta pruning, killer move heuristic)
  • If you find a strong move, there isn't a need to search other moves, hence move ordering for search is vitally important. Killer moves are moves that tend to be best in a wide variety of positions (what we might call a refutation).
  • See Chess Programming Wiki for other popular optimizations in chess and shogi engines
• Bonanza (20-year-old software)
  • In early development, could only search 3 moves deep (5 in endgame); yet it is strong because the code is efficient
  • More modern versions use a greedy search algorithm which is 200,000 times faster. In comparison, other modern shogi engines often search to a depth of 2-3 plies!
• Large shogi AI tournaments (WCSC) held annually since 1990
  • Using tournament results, one can estimate Elo strength of engines (with respect to each other, and/or in comparison to ShogiClub24 ratings).
  • It is believed that the ShogiClub24 human rating limit is about 3000, and in 2009 title holder Watanabe defeated Bonanza (rating estimate 2815).

Current Era (2013 - 2024)

• Supervised "subject-based" learning
  • Bonanza parameter tuning from 30,000 professional players games
  • Too many evaluation parameters, so eventually it tuned parameters from its own game records
• Corporate sponsorship of Shogi Den-O (2013-2017) supported by Dwango Co., Ltd. with 3M¥ first place and 1M¥ second place prize
• World Shogi AI Denryusen (2018 - ) with 1M¥ prize
• YaneuraOu (2015 - ) free software released on GitHub
  • Modular architecture: you can replace evaluation function module, search module, and joseki (opening) module
    • Many developers embraced Unix philosophy (each module should do one thing and do it well, even if modularization is not optimal)
  • I contributed multi-platform build pipelines!
  • More recently, developers collaborate via X and Discord
• Stockfish free software released on GitHub used as a reference for shogi engines
  • Thousands of volunteer developers and a robust self-play test framework
  • Concepts such as "counter-moves" (refutations to specific moves) transcend games. Since chess has so many powerful pieces it's quite difficult for concepts to exist, and therefore it would be strange if concepts which exist in chess didn't exist in other games.
• AlphaZero (2017)
  • MCTS powered by Deep Learning (as a reminder, MCTS uses random numbers to perform many, many simulations, rather than trying to accurately predict the next step at each step in the simulation)
  • Translated captions mention "as of 2024 Alpha Beta Coffee using MCTS is the top shogi AI" although I don't know what this means. How can MCTS be practical for a game with 80 legal moves per position?
• NNUE (2018 - ) backpropagation to optimize layers of parameters thanks to DeepMind / AlphaGo
  • Previously Stockfish relied upon SPSA to optimize a vector of parameters
  • I was elated Google DeepMind released their Stockfish - AlphaZero (2017) research, despite many chess players being upset about match conditions. Had DeepMind hid their research like IBM (Deep Blue) and ChessBase (X3D Fritz), we wouldn't have NNUE as we know it today.
  • nnue-pytorch later developed to use GPU power
• Kristallweizen evaluation function + YaneuroOu (2019) -- 4485
  • NNUE HalfKP-256x2-32-32 type of evaluation function, used within YaneuraOu's search (a Shogi adaptation of Stockfish's search)
• Suisho5 + YaneuroOu (2021) -- 4576
• Tanuki + YaneuroOu (2024) -- 4714 (and stronger on supercomputer hardware!)
• Book How to Make a Strong Shogi Software (2021) authored by dlshogi developer 山岡忠夫, 加納邦彦 著 premise is that conventional AI methods don't work in strong engines, so to make a strong engine you don't need conventional knowledge
  • That same developer released their training data, as has tayayan . He acknowledges that releasing his data could in theory make competition more difficult, however it would be a waste of a treasure to not publish their data. I watch たややんCh.@将棋AI水匠 despite a language barrier because they openly share their research.
  • It is costly to generate parameter values; however, it is far more costly to generate high quality training data used as input to tune parameter values. Releasing this training data lowers the hurdle for new developers to create their own engines!
• Creation of Universal Shogi Interface allows engines to communicate on a variety of GUIs
• "We may imagine that engine opponents may be developing surprise openings ("joseki") based upon professional player habits, but I'm going to skip this part of the talk; I use shogi engines** as a tool."
• Although there are many shogi engines, in practice only a few (such as Suisho) are the most popular, and there aren't large variations in evaluations between similar-generation engines.
  • Consequently, broadcasters like AbemaTV normalize these evaluations to estimate winning chances, since that's easiest to understand.
  • That normalization uses a sigmoid function (in my own experimentation, many sigmoid functions work well, although I hand-picked a value for Lichess' win% estimate).
  • "Why use a sigmoid?" It's an easy to calculate function with smooth, continuous properties; but also, it fits the data!

Future (2025 - )

• Currently, there are two main types of engines: those based upon alpha-beta search, and those using deep learning like dlshogi and AobaZero
  • (oh, so that's what "dlshogi" stands for!)
• A proliferation of source code from free software engines is freely available! So what challenges need to be overcome to make stronger engines?
  • Evaluation function (currently CPU-bound; tradeoff between complexity/speed of evaluation versus more efficient searching)
  • Maybe CNN could be fast and efficient, however CPU registers are small and access to RAM is slow
  • Why can't the CPU offload evaluation work to memory-rich GPUs? With alpha-beta (nonparallel or low parallelism) search, the CPU would be waiting on GPUs to provide a response.
• Apparently dlshogi uses an "improved CNN" using the transformer mechanism used in language models (I'd need to research this).
• Apparently NN evaluation functions use a shallow and simple neural network, so there is limited opportunity for learning; however, reduced evaluation complexity also comes with ability to search faster (if less efficiently), which is fantastic for extremely tactical shogi endgames but less good for nuanced opening strategy.
• In engine versus engine matches, strategies/castles which involve moving the rook horizontally toward the bishop (which are considered defensive in nature) don't score well, so engine developers are hesitant to make engines which try such strategies.
• Currently, opening strategies are collated by hand, not by engines.
  • Shogi isn't chess; there are simply too many opening positions for current-generation software and hardware to solve this problem.
• Can search ideas other than those used by Stockfish also work well for shogi? Similarly, can dlshogi (MCTS) use ideas other than those used in KataGo?
• Access to compute resources is expensive! Thankfully, corporate sponsors defray costs (AMD, HEROZ, Intel)

Shogi AI champions presentation 【将棋AIの基本がわかる/実写映像】CEDEC2024講演「将棋AIの過去・現在・未来」【やねうらお・たややん】
https://youtu.be/TWXP88bTyoQ

Image credit: Oliver Orschiedt
**You might note I use "engine" where colloquially "AI" is used. Shogi engines are powerful tools; however, let's not conflate them with "AI" shovelware routinely marketed to us.