Sage Journals: Discover world-class research

Abstract

Single Conspiracy Number (SCN) is a variant concept of conspiracy number and proof number which indicates the difficulty of a root node changing its MIN/MAX value to a certain score. It makes up the drawbacks of conspiracy number on computing complexity, and can be easily applied into different search frameworks. This paper explores the potential usage of SCN as a long-term position evaluation to understand in-depth game progress patterns. Chinese Chess is chosen as a testbed for this study, whereas a strong AI engine ‘Xiangqi Wizard’ is used. It is implemented with alpha-beta search and modified to produce SCNs during the search process. Experiments are conducted on different types of positions including tactical positions, drawn positions and opening positions. The experimental results show that SCN is more consistent and accurate for long-term position evaluation than the conventional way using evaluation function values only, and using SCN together with evaluation function values enables us to better understand game progress patterns.

Keywords

Single Conspiracy Number MIN/MAX value game progress pattern Chinese Chess

Get full access to this article

View all access options for this article.

References

Allis, L.V., van der Meulen, M. & van den Herik, H.J. (1994). Proof-number search. Artificial Intelligence, 66(1), 91–124. doi:10.1016/0004-3702(94)90004-3.

Khalid, M.N.A., Ang, E.M., Yusof, U.K., Iida, H., et al. (2015b). Identifying critical positions based on conspiracy numbers. In International Conference on Agents and Artificial Intelligence (pp. 100–127). Springer. doi:10.1007/978-3-319-27947-3_6.

Khalid, M.N.A., Yusof, U.K., Iida, H., et al. (2015a). Critical position identification in games and its application to speculative play. In ICAART (pp. 38–45).

McAllester, D.A. (1988). Conspiracy numbers for min-max search. Artificial Intelligence, 35(3), 287–310. doi:10.1016/0004-3702(88)90019-7.

Pawlewicz, J. & Hayward, R.B. (2016). Conspiracy number search with relative sibling scores. Theoretical Computer Science, 644, 127–142. doi:10.1016/j.tcs.2016.06.027.

Plaat, A., Schaeffer, J., Pijls, W., et al. (1996). Best-first fixed-depth minimax algorithms. Artificial Intelligence, 87(1), 255–293. doi:10.1016/0004-3702(95)00126-3.

Schaeffer, J. (1990). Conspiracy numbers. Artificial Intelligence, 43(1), 67–84. doi:10.1016/0004-3702(90)90071-7.

Song, Z. & Iida, H. (2017). Using single conspiracy number to analyze game progress patterns. In 2017 International Conference on Computer, Information and Telecommunication Systems (CITS), Dalian (pp. 219–222). doi:10.1109/CITS.2017.8035312.

Vu, Q., Ishitobi, T., Terrillon, J.C., et al. (2016). Using conspiracy numbers for improving move selection in minimax game-tree search. In ICAART.

Using single conspiracy number for long term position evaluation

Abstract

Keywords

Get full access to this article

References