Abstract
The UCT algorithm has gained popularity for use in AI for games, especially in board games. This paper assess the performance of UCT-based AIs and the effectiveness of augmenting them with a lookup table containing evaluations of games states in the game of Chinese Checkers. Our lookup table is only guaranteed to be correct during the endgame, but serves as an accurate heuristic throughout the game. Experiments show that using the lookup table only for its endgames is harmful, while using it for its heuristic values improves the quality of play. This work is performed on a board with 81 locations and 6 pieces, which is larger than previous work on lookup tables in Chinese Checkers. It is a precursor to using the 500 GB full-game single-agent data on the full-size board with 81 locations and 10 pieces.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Audouard, P., Chaslot, G., Hoock, J.-B., Perez, J., Rimmel, A., Teytaud, O.: Grid coevolution for adaptive simulations: application to the building of opening books in the game of Go. In: Giacobini, M., Brabazon, A., Cagnoni, S., Di Caro, G.A., Ekárt, A., Esparcia-Alcázar, A.I., Farooq, M., Fink, A., Machado, P. (eds.) EvoWorkshops 2009. LNCS, vol. 5484, pp. 323–332. Springer, Heidelberg (2009)
Browne, C., Powley, E.J., Whitehouse, D., Lucas, S.M., Cowling, P.I., Rohlfshagen, P., Tavener, S., Perez, D., Samothrakis, S., Colton, S.: A survey of monte carlo tree search methods. IEEE Trans. Comput. Intell. AI Games 4(1), 1–43 (2012)
Chaslot, G.M.J.-B., Hoock, J.-B., Perez, J., Rimmel, A., Teytaud, O., Winands, M.H.M.: Meta monte-carlo tree search for automatic opening book generation. In: Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, 2009, pp. 7–12 (2009)
Coulom, R.: Efficient selectivity and backup operators in Monte-Carlo tree search. In: van den Herik, H.J., Ciancarini, P., Donkers, H.J. (eds.) CG 2006. LNCS, vol. 4630, pp. 72–83. Springer, Heidelberg (2007)
Kocsis, L., Szepesvári, C.: Bandit based Monte-Carlo planning. In: Fürnkranz, J., Scheffer, T., Spiliopoulou, M. (eds.) ECML 2006. LNCS (LNAI), vol. 4212, pp. 282–293. Springer, Heidelberg (2006)
Lorentz, R.J.: Amazons discover Monte-Carlo. In: van den Herik, H.J., Xu, X., Ma, Z., Winands, M.H.M. (eds.) CG 2008. LNCS, vol. 5131, pp. 13–24. Springer, Heidelberg (2008)
Nijssen, J.A.M., Winands, M.H.M.: Playout search for Monte-Carlo tree search in multi-player games. In: van den Herik, H.J., Plaat, A. (eds.) ACG 2011. LNCS, vol. 7168, pp. 72–83. Springer, Heidelberg (2012)
Samadi, M., Schaeffer, J., Torabi Asr, F., Samar, M., Azimifar, Z.: Using abstraction in two-player games. In: ECAI, pp. 545–549 (2008)
Schadd, M.P.D., Winands, M.H.M.: Best reply search for multiplayer games. IEEE Trans. Comput. Intell. AI Games 3(1), 57–66 (2011)
Schaeffer, J., Björnsson, Y., Burch, N., Lake, R., Lu, P., Sutphen, S.: Building the checkers 10-piece endgame databases. In: van den Herik, H.J., Iida, H., Heinz, E.A. (eds.) Advances in Computer Games 10, pp. 193–210. Springer, New York (2003)
Sturtevant, N.R.: A comparison of algorithms for multi-player games. In: Schaeffer, J., Müller, M., Björnsson, Y. (eds.) CG 2002. LNCS, vol. 2883, pp. 108–122. Springer, Heidelberg (2003)
Sturtevant, N.R.: Last-branch and speculative pruning algorithms for max\(^{\text{ n }}\). In: Gottlob, G., Walsh, T. (eds.) IJCAI, pp. 669–678. Morgan Kaufmann (2003)
Sturtevant, N.R., Rutherford, M.J.: Minimizing writes in parallel external memory search. In: International Joint Conference on Artificial Intelligence (IJCAI), pp. 666–673 (2013)
Thompson, K.: Retrograde analysis of certain endgames. ICCA J. 9(3), 131–139 (1986)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Roschke, M., Sturtevant, N.R. (2014). UCT Enhancements in Chinese Checkers Using an Endgame Database. In: Cazenave, T., Winands, M., Iida, H. (eds) Computer Games. CGW 2013. Communications in Computer and Information Science, vol 408. Springer, Cham. https://doi.org/10.1007/978-3-319-05428-5_5
Download citation
DOI: https://doi.org/10.1007/978-3-319-05428-5_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-05427-8
Online ISBN: 978-3-319-05428-5
eBook Packages: Computer ScienceComputer Science (R0)