Minimax / AlphaBeta harness

dragonchild has asked for the wisdom of the Perl Monks concerning the following question:

Replies are listed 'Best First'.
Re: Minimax / AlphaBeta harness by hsmyers (Canon) on Jul 18, 2003 at 00:20 UTC
I haven't seen anything like that---however I admittedly wasn't looking, since my interest is in manipulating the result of playing chess, i.e. the games themselves. However, there is now a perl-chess list hosted at Yahoo. Join with email to perl-chess-subscribe@yahoogroups.com. I believe that there has been a recent discussion about current AI technique and chess and I think I remember a reference to other groups that might provide a better search territory. --hsm "Never try to teach a pig to sing...it wastes your time and it annoys the pig."	[reply]
Re: Minimax / AlphaBeta harness by pernod (Chaplain) on Jul 18, 2003 at 08:09 UTC
I would assume that you have already seen these, but it seems to me that Graph::Base and Meta::Graph::Directed might take you some steps in the right direction. As a tree-structure is a special case of directed graphs, it should not be too difficult to construct a tree using these modules. From the pod in Meta::Graph::Directed This class is here to provide a place to add method to the Graph::Directed module available from CPAN. I know that Graph::Directed looks pretty nice but still if I need any convenience methods or maybe a small algorithm or two it will be nice to add them at the graph level. Perhaps too bare-bones, but at least a suggestion. I haven't used the module myself, though, so administer the required grains og salt. Good luck :) pernod -- Mischief. Mayhem. Soap.	[reply]
Re: Minimax / AlphaBeta harness by wufnik (Friar) on Jul 18, 2003 at 15:11 UTC
hola dragonchild, there are no modules i know of that implement the simplex algorithm (or other LP solving technique), which you will need to solve the optimal strategies for the players of your games (provided you have a pay off matrix). mastering algorithms in perl also draws a blank. i may be able to help, but i need to know the type - the game theoretic type - of the game you are considering. ie: is it 2 person, zero sum (hope so ;-)), or more complex. if you have a player's chosen move, determining the best move of the other player is trivial, but i don't want to second guess you; go on, tell us more... regards, wufnik -- in the world of the mules there are no rules --	[reply]
Re2: Minimax / AlphaBeta harness by dragonchild (Archbishop) on Jul 18, 2003 at 15:29 UTC
As a personal project, I'm working on extending Simon Cozens Games::Goban module to include referees for various games, as well as basic AI modules for each game. I am trying to build a basic minimax harness that I can use with each of the various game types. More detail: All the games are 2-player games. I don't believe that they are necessarily zero-sum games. (For example, I don't think that go is necessarily zero-sum, and go-mo-ku isn't, either.) All games are perfect information, back-and-forth games. They also all run on the same type of game state, so I plan on allowing this harness to specialize to that gamestate. I most certainly can determine a pay-off matrix for each player's moves. (That, in fact, is the ultimate fun of this project - figuring out payoff matrices for Go in Perl. grins) So far, I've built a referee and basic AI for Othello and am working on implementing NxN Tic-Tac-Toe. I'm using those as the simpler AI's and referees to build. Then, I want to build Go. ------ We are the carpenters and bricklayers of the Information Age. Don't go borrowing trouble. For programmers, this means Worry only about what you need to implement. Please remember that I'm crufty and crochety. All opinions are purely mine and all code is untested, unless otherwise specified.	[reply]
Re: Re: Minimax / AlphaBeta harness by chunlou (Curate) on Jul 19, 2003 at 20:08 UTC
What about Math::LP? Though no one said that the minmax problem was a LP one.	[reply]
Re: Re: Re: Minimax / AlphaBeta harness by wufnik (Friar) on Jul 21, 2003 at 07:33 UTC
thanks chunlou this module escaped me. i use the gnu linear programming kit, not lp_solve; GLPK compiles well on cygwin, as you'd expect, but there are no perl wrappers for it, again as far as i know. lp_solve does not compile on cygwin, and i expect it will not on linux either given the host of warnings i got when trying to compile it. NB: i tried the module first, which failed to install, so i went straight for lp_solve, tried to compile it too - and this is where the real problems kicked in (flex errors). these are too much for me at 830am. maybe later... i would be interested in the experiences of others in getting the Math::LP modules to work, as they look very useful, but i cannot achieve function under win32. has anyone else hacked them to work on this environment? minimax is not LP, but finding your optimal strategy given a pay-off matrix is. it was this i was hoping to get dragonchild, but my hopes are receding... thanks for any comment, wufnik -- in the world of the mules there are no rules --	[reply]