   AI for an old Nim-like game
  I'm going to end up with 3 threads for this thing, but I want maximum exposure.101 BASIC games had a program called Chomp that was in its own way like a 2D version of Batnum (Nim to some) sans the "perfect" computer opponent. I've rewritten it for a little side project of mine (that I'll be pumping up some day soon I hope) and added one little aspect, the maximum bite, to make it more like a 2D Batnum.However, now I don't know what the perfect game looks like. The listing on my rewrite includes the executable and source file so you can try it out even if you don't have the ability to compile C++. You don't have to flesh the stub compymove () if you don't want to. Just describe how it should work.Are there any geniuses out there who can figure this one out? I suspect that like Batnum or Nim a perfect game exists (and without the mamimum bite it's actually pretty simple), I just haven't taken the time to figure it out.[Edited by - guesst on January 1, 2008 1:47:03 PM]
  Nim-like games are usually analyzed by computing the "nimbers" (Nim numbers) that correspond to each possible game situation (see the Sprague–Grundy theorem).Once you understand how nimbers work, you should be able to give the problem a dynamic-programming solution.;Quote:Original post by alvaroNim-like games are usually analyzed by computing the "nimbers" (Nim numbers) that correspond to each possible game situation (see the Sprague–Grundy theorem).Once you understand how nimbers work, you should be able to give the problem a dynamic-programming solution.Hmmm, perhaps I misrepresented the problem with my thread title. I know nimbers and nim sums. I'm in the middle of writing a game of Nim. Admitedly I still have some to learn, however did you look at the game? It has a unique problem that, unlike Nim, is played in 2Ds at once. While my implimentation of it esentally treats each row like a number of things, you take, esentally, from multiple rows at once.I've got to go, but check out http://www.retroremakes.com/forum2/showpost.php?p=153402&postcount=34 for more information.Oh, I'll be racking my brain on it too, don't think I'm just coping out. I just figured more heads are better than mine.   ;  Yes, I understand the game. A game configuration can be described by a decreasing list of numbers that represent the length of each row. You can compute the nimber of each configuration in a dynamic-programming style.For instance, you can loop over all configurations with 1 stone, 2 stones, 3 stones... and for each one of them, you see what smaller configurations it can be converted to. If something can be converted to nimbers 0, 1, 2, ... and n-1 but not n, its nimber is n. If it cannot be converted to 0, the nimber is 0.Actually, in this game it is enough to compute whether the nimber is 0 or not (whether the player to move losses or wins), since the game is never decomposed into subgames.Write again if this didn't make much sense.   ;  A Google search on Sprague–Grundy theorem led to wikipeda. Following a link on impartial games wherein Chomp is actually mentioned (!) (which I don't know why I didn't find before), which led to a plethora of resources, my favorate being the one that statesQuote:Existence of a winning strategyIf P has a largest element 1, different from 0, then a trivial strategy-stealing argument shows that the first player wins. (If picking 1 does not win, it is because the opponent has the devastating reply a. But in that case the first player wins by starting with a.)However, the argument is non-constructive: the winning move is unknown. (Emphasis added.)I had to wade through alot of the sort of graduate level peenee waving that gets doctoral degrees without actually solving problems and bugs the h-e-double-hockey-sticks out of me.Dispite Wikipedia's "authorativive" statement Quote:Computers can easily calculate winning moves for this game on two-dimensional boards of reasonable size....it seems the only solutions from the game are for fixed sizes and not very dynamic at all. http://www.philipbrocoum.com/munch/winners8x9.txt seems a good resource for analizing the nim numbers that could perhaps be generalized and I'll probably spend a long, long time looking at this list.I think the verticle and horizontal nim numbers need to be compared or perhaps calculated together in some way, but I'm not sure yet. The quest still continues.[Edited by - guesst on January 1, 2008 1:22:00 PM];  I implemented a minimax function with memory, and it solved the 9x9 case really really fast. If you want actual code, I can provide it later.   