Hi there! First post here. I'm doing some kind of go game and I have no idea how to make the CPU to take decisions about where to put the stones in the board…

I'm a web developer and this aspect of programming is completely unknown to me, so… Where should I begin? Any piece of advice? Book to read? Tutorial?

I don't know about the game Go, but for most board games you just need to have a set of rules the computer player follows based on the current state of the board.

For example there are a set of rules you can follow when you play tic-tac-toe that will ensure you never lose:
https://en.wikipedia.org/wiki/Tic-tac-toe

Create a similar ruleset for your go game. Have it check for certain things to be true in order of importance till finally you have the computer player just opt for a random move if none of it's rules are met.

Hmm if you've never done AI before (is that what you are saying?), Go is a really super hard place to start. Are you aware of the recent news of Google making the first AI that could beat expert Go players?

http://googleresearch.blogspot.com/2016/01/alphago-mastering-ancient-game-of-go.html

Basically the only way to do decent AI with Go is to use a technique called machine learning, which would probably require more data storage than is feasible on PICO-8, and is way more complicated than a simple AI algorithm for something like Tic-Tac-Toe, which would be my recommendation for a good place to start :)

However, I imagine you could make a simple Go AI that would not beat expert players :)

To be honest… It's no Go actually: I've reduced board size to 6x6 and I was thinking on give a win to the first player who can put 4 in a row… That easy.

I just don't want the CPU to choice dumb decisions, at least at the first approach of the game.

Game trees might be a good route. They are the only piece of AI I understand really, as they're incredibly simple. Basically the computer will look at every single possibility for a next move and a next next move and chose its move based on that. With games like chess this can result in a massive tree that needs to be trimmed, which is a difficult process, but with your reduced board size you might not need to do that.

Even simpler than game trees is expert systems, where you look at every board configuration manually and have preset AI decisions based on that. But the number of paths in the game must be significantly smaller for that to be a viable option.

OK, let me tell you a bit about minimax.

First approach: every turn, the CPU calculates a heuristic for the board - in your Gomoku variant, let's give each side 1 point for a line with two pieces and a free space on either side, 3 points for a line with three pieces and one free space on one side, 99 points for a line with three pieces and free spaces on both sides (victory-assured position) and 999 points for a line with four pieces (victory position)

Now for the CPU's move, it chooses the move that maximizes its heuristic (which is the CPU's score minus the player's score).

This is a zero-ply, or zero-move lookahead. Let's try to look ahead one move - we're predicting what the human player might do on their turn.

Logically, the human wants to maximize their heuristic score. So, for every possible move the CPU can do, we look at what the next human move will be to make their score the best score possible.

Out of all these scores, we want to choose the CPU move that will make the worst world possible for the human. That's what minimax means - the CPU wants to minimize the maximal possible move of the human.

Larger lookaheads keep working the same way: assume the human will always do the best move possible under any circumstances, and choose the CPU move that will make that best move not all that good.

Yeah, those heuristics would actually be a pretty easy way of trimming the game tree.

I added pico4 in WIP cartridges, a 4 in a row game with an AI that uses minmax algorithm. It,s a bit slow but it works well. You can change (manually in the code yet) the depth.

Artificial intelligence remains a fascinating topic with its transformative potential across various sectors. In education, platforms like Edubirdie offer essential support to students seeking assistance with research papers or essays. Reading reviews at https://www.reviews.io/company-reviews/store/edubirdie.com can help students find the best writer suited to their needs. Leveraging such resources responsibly ensures students receive quality guidance, enhancing their learning journey and academic achievement.