Zeta Chess

Zeta - Source Code and Binaries online

I fixed some issues in Zeta and Zeta Dva, source code and binaries are online again



Please read the whole README file before running the Zeta engine on GPU


I lost the source of Zeta Vintage, and an attempt to do an rewrite in C showed again that the 6502 processor should really be programmed in assembly, so a rewrite in 6502 assembly is still on my bucket list...



To port an classic chess engine approach with an parallel Alphabeta algorithm like YBWC to an GPU architecutre would take a significant bunch of time, if it is even possible to port all well known computer chess techniques straight forward. And it is questionable if an Elo gain, by more computed nodes per second, is eaten up again by an higher branchingfactor due to an simpler implementation.

Zeta 098 and 097 make use of an Randomized Best First MiniMax Search, but my implementation makes excessive use of Global Memory and scales poorly.

At the very beginning of the project it was clear, that an Monte Carlo Tree Search would fit best for gpus. But until now there is no known engine that could make MCTS work well for Chess.

What is left, except to try to port an classic approach?

I could improve the performance of the BestFist search significantly by switching from GlobalMemory to LocalMemory and i could remove the randomness...another alternative would be to switch to MCAB, Monte Carlo Alphabeta...

Zeta v099

I finished my current run on Zeta v099, my experimental gpu chess engine.


The actual conclusion of the current iteration is, that an simple engine, with standard chess programming techniques, can be ported to OpenCL to run on a gpu, but it would take more effort to make the engine competitive in terms of computed nodes per second (speed), heuristics (expert knowledge), and scaling (parallel search algorithm).

Computer Chess, as an computer science topic, evolved over decades, starting in the 40s and 50s, and reached one peak 1997 with the match Deep Blue vs. Kapsarow. Nowadays chess engines are tuned by playing thousands and thousands of games, so to get an chess playing engine running on the gpu and to get an competitive chess playing engine running on the gpu are two different tasks.

How Computer Chess Engines could run on GPUs

  1. One SIMD Unit - One Board
    To avoid thread divergence in a Warp, resp. Wavefront, the engine could couple, for example, 32 or 64 Work-Items of one Work-Group to work together on the same chess position. For instance, to generate moves, sort a move list or do an board evaluation in parallel. A move generator of such an Work-Group could operate over pieces, directions, or simply 64 squares in parallel. But in any of these cases current GPU SIMD units will 'waste' some instructions compared to the more efficient, sequential, processing of an CPU.
  2. Use of Local Memory* instead of Global Memory
    The more sequential threads are coupled into one Work-Group to work on one chess position in parallel, the more Local Memory* per Work-Group could be available to store a move list, or a move list stack. By the use of faster Local Memory ,less Warps (resp. Wavefronts) are in need to hide Global Memory latency.
  3. Hundreds of Work-Groups instead Thousands of Threads
    YBWC is a parallel game tree search algorithm used in nowadays chess engines, but the more workers the algorithm runs, the less efficient he performs.So, by coupling sequential operating threads into one Work-Group, to work on one chess position in parallel, we lower the total number of workers and increase efficiency of the parallel search.

* Local Memory as OpenCL term is translated to Shared Memory as Nvidia Cuda term.

Zeta - Milestones

Here an overview of what happened before....

Zeta (099h to 099k)

  • fixes n cleanups
  • switch from Lazy SMP to ABDADA parallel search
  • added IID - Internal Iterative Deepening
  • one cl file for all gpu generations with inlined optimizations
  • Zeta 099k on AMD Radeon R9 Fury X, 256 workers, ~ 7.6 Mnps
  • Zeta 099k on Nvidia GeForce GTX 750, 16 workers, ~ 800 Knps
  • Zeta 099k on AMD Radeon HD 7750, 32 workers, ~ 700 Knps
  • Zeta 099k on Nvidia GeForce 8800 GT, 14 workers, ~ 110 Knps

Zeta (099b to 099g)

  • switch from KoggeStone based move generation to Dumb7Fill
  • added atomic features for different gpu generations

Zeta (099a)

  • switch from best first minimax search to parallel alphabeta (lazy smp)
  • ported all (except IID) search techniques from Zeta Dva v0305 to OpenCL
  • ported the evaluation function of Zeta Dva v0305 to OpenCL
  • vectorized and generalized 64 bit Kogge-Stone move generator
    64 threads are now coupled to one worker, performing move generation,
    move picking and evaluation, square-wise, in parallel on the same node
  • portability over performance, should run on the very first gpus with
    OpenCL 1.x support (>= 2008)

Zeta (098d to 098g)

  • mostly cleanup and fixes
  • restored simple heuristics from Zeta Dva (~2000 Elo on CCRL) engine
  • protocol fixes
  • fixed autoconfig for AMD gpus
  • switched to KoggeStone based move generator
  • switched to rotate left based Zobrist hashes
  • switched to move picker
  • switched to GPL >= 2
  • Zeta 098e on Nvidia GeForce GTX 580, ca. 6 Mnps, est. 1800 Elo on CCRL
  • Zeta 098e on AMD Radeon HD 7750, ca. 1 Mnps
  • Zeta 098e on AMD Phenom X4, ca. 1 Mnps
  • Zeta 098e on Nvidia GeForce 8800 GT, ca. 500 Knps

Zeta (098a to 098c)

  • Improved heuristics, partly ported from the Stockfish chess engine
  • AutoConfig for OpenCL devices
  • Parameter tuning
  • Zeta 098c on Nvidia GeForce GTX 480, ca. 5 Mnps, est. 2000 Elo on CCRL
  • Zeta 098c on AMD Radeon R9 290, ca. 3.2 Mnps

Zeta (097a to 097z)

  • Implementation of an BestFirstMiniMax search algorithm with UCT parameters for parallelization
  • Zeta 097x on Nvidia GeForce GTX 480, ca. 5 Mnps, est. 1800 Elo on CCRL
  • Zeta 097x on AMD Radeon HD 7750, ca. 800 Knps

Zeta (0930 to 0960)

  • Tested Monte Carlo Tree Search without UCT across multiple Compute Units of the GPU
  • Tested LIFO-Stack based load balancing for AlphaBeta search on one Compute Unit of the GPU
  • Tested the 'Nagging' and 'Spam' parallelization approach for AlphaBeta search on one Compute Unit of the GPU
  • Tested 'RBFMS', Randomized BestFirstMiniMax Search, a parallelized version of BestFirstMinixMax, across multiple Compute Units of the GPU

Zeta (0915 to 0918)

  • 64 bit Magic Bitboard Move Generator running
  • AlphaBeta search algorithm with 'SPPS'-parallelization running 128 threads on one Compute Unit of the GPU

Zeta (0900 to 0910)

  • Tested 32 bit 0x88 and 64 bit Magic Bitboard Move Generator
  • Ported Heuristics, the Evaluation Function, from CPU engine 'ZetaDva' (~2000 Elo) to OpenCL


* updated on 2018-11-13 *

Zeta - Source Code

Zeta and Zeta Dva support only some basic Xboard protocol commands and some users have reported problems with the configuration and interface of the last Zeta versions.‭ ‬So i will publish the source code again when these parts are more user friendly designed and tested for Windows Chess-GUIs like Winboard or Arena.

Home - Top