search

JohnAD / negamax

negamax AI algorithm for turn-based games
13 stars 1 forks source link

Speed [Question] #4

Open d-motzer opened 9 months ago

d-motzer commented 9 months ago

Hi @JohnAD,

did you ever get around to finishing the non-recursive version? I'd love to try out the optimization

JohnAD commented 9 months ago

Sadly, no. And my time is booked solid for the next 4-plus months, perhaps more.

The optimization does make a huge difference for many game scenarios; remembering my time writing games in Python and C#.

Here is the non-recursive algo in Python: https://github.com/Zulko/easyAI/blob/master/easyAI/AI/NonRecursiveNegamax.py

If you end up writing a non-recursive variant in Nim, I'm happy to take a PR and merge it with this repo and add you as a maintainer.

Fair warning though: most algorithms have border and "off-by-one" conditions to watch out for. This algo is almost 100% border conditions. It isn't pretty or flexible. I strongly recommend writing and running a few games with the recursive version to captuer output and compare against the non-recursive version to verify it doesn't go off the rails.