Game tree tutorial on Swish

Following on from my graph traversal tutorial at https://swish.swi-prolog.org/p/Graphs1.swinb, I’ve elaborated the code to handle adversarial search at a tutorial at https://swish.swi-prolog.org/p/minimax19.swinb

It’s still work in progress, and only has two easy tic-tac-toe examples so far. I’m planning to develop it further to use iterative deepening with alpha-beta pruning in due course, but it’s far enough for anyone interested in AI basics to tinker with.

Comments and suggestions welcome as always, since I’m doing it as much for my own education as others.

(BTW: I’ve had to change the url from Games, to Games1, Games2 … to minimax because Swish constantly prevents me from saving for some reason. I’m hoping not calling it GamesN will help since I’m guessing its a popular name).

2 Likes

I’ve made an initial attempt at iterative deepening with pruning the game tree as the picture gets clearer. There are only two easy tic-tac-toe examples so far (I tried to include a tougher example, and am worried I crashed the server, though it seems to have recovered.).

I’ve been battling with saving, and needed to keep changing the name. Not sure I’m doing something wrong. The old problem was I wasn’t putting in comments when saving new versions, but that’s not the reason now.

The most current version is at https://swish.swi-prolog.org/p/minimax19.swinb

After many hours and rewrites I’ve got my game tree solver to figure out the moves to force a draw in this tic-tac-toe board:

 X |   | 
---+---+---
   | O |   
---+---+---
   |   | 

I’ve had these weird problem with the swish site that it refuses to let me update this tutorial (though I don’t know what I’ve done different to the others that it let me update) so the current URL is https://swish.swi-prolog.org/p/minimax19.swinb

I’m still battling to figure out how to tell the iterative deepening predicate when to quit searching, so it cuts out too early for the two puzzles I’ve included, but hope to sort that out in due course.

I’ve appended this tutorial to my graph traversal tutorial at https://swish.swi-prolog.org/p/Graphs1.swinb

I’ve merged them partly because I got the search predicates to handle 1 to N players to use a common code base, and also because for some reason (not sure which box I ticked wrong), swish wouldn’t let me update the file I used for games without renaming it.