Title: A faster algorithm for calculating evaluation function in Hex game

Authors: Ze Liu; Yi Wang; Bin Wang; Puyuan Du; Yungang Zhu

Addresses: College of Computer Science and Technology, Jilin University, Changchun, 130012, China ' College of Computer Science and Technology, Jilin University, Changchun, 130012, China ' College of Computer Science and Technology, Jilin University, Changchun, 130012, China ' College of Computer Science and Technology, Jilin University, Changchun, 130012, China ' College of Computer Science and Technology, Jilin University, Changchun, 130012, China

Abstract: Queenbee is an exceptional evaluation function in search-based AI algorithms for Hex. It assesses each empty cell on the board by calculating a unique metric known as 'Two-distance', traditionally determined via a breadth-first search with O(n²) time complexity. In this paper, we introduce the Contour Line Algorithm (CLA), which reduces the time complexity to O(n) without increasing space complexity. CLA computes the Two-distance for each cell layer by layer, treating connected blocks of cells with identical Two-distance values as contour lines. Experimental results show that CLA significantly outperforms the traditional approach.

Keywords: Hex game; evaluation function; computer gaming; contour line algorithm.

DOI: 10.1504/IJCSM.2025.149908

International Journal of Computing Science and Mathematics, 2025 Vol.22 No.2, pp.129 - 139

Received: 02 May 2023
Accepted: 05 Jul 2024
Published online: 17 Nov 2025 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article