Looking for some tutorials on how to handle AI for board games. From what I’ve looked up so far, all of the tutorials are in regards to using the navmesh and attack-based AI structure. Is there a good starting point on how to handle board games? I would eventually like to learn how to implement an MCTS with UCT and Pattern recognition (CUDA-based deep neural networking).
Well, I’ve done some self-research and work on it, and here is what I have so far:
- Grid generation (player selects): 9x9, 13x13, 19x19 grid
- I’m handling the coordinates using Vector2D variables (max_grid and grid_location) and a V2D array (grid_array). These store intersecting points, such as 1,1 / 1,17 / 15, 13 / etc…
- I’m using a Vector3 array to handle which intersection belongs to what player. So if Player1 puts a piece at 5,18 then it will be stored in the array as 5,18,1. There are 2 different arrays handling this, an “empy location” array and a “used location” array
- Max play time / time remaining system
For the actual “AI” part of it, I have reconstructed:
UCB algorithm system (http://www.cameronius.com/research/mcts/about/index.html)
– (wins/simulations) + Bias * SqRt (loge(parent_visited)/(child_visited))
Value-Situational Handicap Compensation (http://www.pasky.or.cz/go/dynkomi.pdf)
– Section 5.1.2 in the above paper
Still working on how to implement those 2 systems for the AI to place pieces, but it’s coming along I guess :\
It’s all about generating a list of logical moves, evaluate each move in the list of moves and choosing from that list, select the most valuable move. Board game AI’s can either be super specific, OR you can implement something that is REALLY dumb like a reinforcement learning ai, which will learn to play the game, but as time goes on, it will incrementally get better.
Edit: i mean ai is super lengthy topic. but other areas you might be interested in is genetic algorithms and neural nets, mcts is awesome i love montecarlo methods, but generally, if i can get away with just two moves ahead calculation, in a board game i’d go for that.
Thanks! I’ll take a look at it tomorrow when I wake up