Minimax and variations (take two)
by John Pritchett · in Technical Issues · 03/30/2005 (3:16 pm) · 0 replies
Ok, now that I've been given a corrective smack by an admin, I got this post in the right area...
One thing I'd like to do with T2D is implement some of my abstract boardgame designs. To do this properly, all I need is a good move scanning algorithm, preferably something that's generalized and can be plugged into a number of different games without having to recode the scan routine every time. I've created a number of my games in Zillions of Games, which provides a nice, general purpose AI for playing "full information" games like Chess. But ZOG is a terrible tool for building games, so limited, and the only thing keeping me from implementing everything I need in my own board game creation tool is a generic search algorithm.
Minimax itself is so basic that it's pretty easy to wire it into any 2 player game. But then you start adding all of the variations; AlphaBeta, NegaScout, quiescent search, etc, and it quickly becomes a complex behemoth. And yet, all that need be exposed to a generic game is a scoring routine, something that takes a given piece configuration and attaches a numeric score to it for comparison with other positions. So theoretically, it is possible to devise a full-featured AND agnostic game search algorithm, that others could just plug into their games and simply provide a hook to their unique scoring code.
I've actually hacked together a functional, deep searching algorithm for one game, but I never quite got my mind around what it was doing enough to generalize it. Does anyone have enough mastery of this kind of algorithm that they could a) tell me if that's possible and if not, why not, and b) actually present such a piece of work to this community? It would certainly knock down the barrier I've hit with a boardgame construction toolkit I've developed, and I'm sure others would find it useful as well.
Thanks!
One thing I'd like to do with T2D is implement some of my abstract boardgame designs. To do this properly, all I need is a good move scanning algorithm, preferably something that's generalized and can be plugged into a number of different games without having to recode the scan routine every time. I've created a number of my games in Zillions of Games, which provides a nice, general purpose AI for playing "full information" games like Chess. But ZOG is a terrible tool for building games, so limited, and the only thing keeping me from implementing everything I need in my own board game creation tool is a generic search algorithm.
Minimax itself is so basic that it's pretty easy to wire it into any 2 player game. But then you start adding all of the variations; AlphaBeta, NegaScout, quiescent search, etc, and it quickly becomes a complex behemoth. And yet, all that need be exposed to a generic game is a scoring routine, something that takes a given piece configuration and attaches a numeric score to it for comparison with other positions. So theoretically, it is possible to devise a full-featured AND agnostic game search algorithm, that others could just plug into their games and simply provide a hook to their unique scoring code.
I've actually hacked together a functional, deep searching algorithm for one game, but I never quite got my mind around what it was doing enough to generalize it. Does anyone have enough mastery of this kind of algorithm that they could a) tell me if that's possible and if not, why not, and b) actually present such a piece of work to this community? It would certainly knock down the barrier I've hit with a boardgame construction toolkit I've developed, and I'm sure others would find it useful as well.
Thanks!
About the author
Indie developer since 1994, games include TradeWars 2002 (named 10th best PC game of all time by PCWorld magazine), TW: Dark Millennium/Exarch/Dungeon Runners, and Rocketbowl 360. Have worked for Martech Software, 21-6, EIS and Black Squirrel Studios.
