I'm interested in making an AI for collapse but initialy the easiest I can think of is trial and error, it picks a random starting pos (if there are multiple cases where two of the same block are next to each other) and goes from there until it's done, recordes it's moves and then tries again, not repeating what it did and reccording the best result it gets in each case. My question is wether someone knows of a better method to do this or not, and if someone knows of a good method for storing moves (psuedo code or C++). The AI will have full view of all the blocks so there is no info hidden from it. for those that don't know what collapse is it's a game where a grid of say 12x10 blocks are shown, and there are 5 possible colours for a given block, the objective of the game is to select blocks that have a neighbour of the same colour in such a way that you will line up a larger combination, the more blocks destroyed per click the better, until the screen is cleared.

I would make a struct that hold the x and y of the move, if it got rid of blocks, how many, or anything that could come in handy.

Also, you should make an algo that looks at each block, and then looks at the four blocks around it. Record the position where there is the highest number of blocks around, by looping throuhg each block. Then have the AI choose that block.

If you wanted to get more complicated, then whenever there is a same colored block next the the one you are on, move to that block and check, and so on. Just keep track of how many moves it makes, without going over the same block twice, and it can find the best possible move.

I wouldn't make it random, as it will make very stupid choices often.

Hmmm I was thinking of a tree node approach, where each click is a node,how ever this seems to be tending towars massiveness realy fast :) memory usage would go through the roof right now, but I can think of a few things to cut it down. (in the order of 100's of megs if I'm lucky)

and if I can figure out a way to give it some brains it would mabe come down to <100 megs at a worst case

Nah, won't be that block. Cycling through each block is not a bad idea for a start. Since its only 12x10, we're only looking at 120 blocks to begin with. You can simply do an exhaustive search.

1. Start with a block.
2. calculate how many blocks will disappear if you click on it. If a block can't be legally made to disappear, then just give it a 0.
3. move on to the next block.
4. click on block that can make the most disappear

This is probably the simplest method, and you'll probably want to do the search from bottom up. Ignore any space that has no block present and your search will take up less and less space. This is, of course, the greedy method.

The smarter way is to factor in diversity of the resulting setting when you make a set of blocks disappear. You want to give favor to settings that have higher levels of clustering. This can be used as a tie breaker or an add-on bonus or penalty to a block's fitness.

However, keep in mind that this may get you a pretty good solution, but probably not the best.

The VERY best way you can do it, without breaking the memory bank on storing states and stuff, is to modify an Ant Colony Optimization to do the search for you. But explaining will take a very long post, so I'll leave it at this for now.

lol yours still sounds like what mine does, with a few slight mods.

This ant colony thing intrigues me so I will do some research on it and see what I can come up with :) but here's a better description of what I want to do:

I initialy was just going to brute force the whole thing with a method like hte one you mentioned, it would see what combinations there where and how they would affect teh cominations next turn, and then make a decision, how ever I came upon the same conclusion you did, this was just not going to work.

My next and current idea was something based of a binary tree, except instead of only 2 branches splitting off per node I would have as many branches as there combinations, so if there where 5 possible clicks on the first try that means the first node (initial state) would have 5 nodes, and each of those nodes would have the number of nodes of combinations in their state, say node 2 has 6 combinations because of the click it represents in node 1 (initial), this means 6 more branches , this proccess of branching out would take place until there where no more combinations in the current path, then the program would back track through the tree branches until it finds one that has a node that needs to be explored, this would keep occuring until it had explored all the combinations that branch off from node 2, it would record what the highest score was for node 2 then move on to node 3.

this proccess would repeat for all nodes, to save on memory an "unsatisfactory" score would be defined and if a specific branch of nodes was fully explored and yieled this it would drestroy it'self back to a node that was either still satisfactory or needed more exploration.

by "back track destruction" memory would be reclaimed. The hardest part of this is that each "node" has to save the state the array was in when it was created, this means that each node is a minimum 1KB (-_-') 120*8+memory for object (each node would be an instance of a node object)

this is the ultimate brute forceing method I came up with :) but as you can see it has flaws, and some of these could be reduced by adding more complex logic calculations to each graph scan.

I'll investigate the ant thing once I catch up in calculus class ;)

Well, if you write the tree thingy recursively and then just pass the new state into the next recursion, you won't have to worry about destroying anything along the way, since as soon as the recursion starts to un-stack, the stuff will be destroyed automatically. Just remember to keep track of the list of best moves so far in a stack as well, or an array. Then you should be able to do it exhuastively.

The problem itself has a state tree that reduces in branching factor as the moves are made. So, on average, the branching factor of the tree further down the line will be much smaller. This is very unlike games like Chess that has a branching favtor that increases as the game proceeds just because of the availability of more possible moves.

how is reducing a problem? that means that I can single out a final move without needing to implement any realy special rules :)

oh and if anyone has links/refs to this ant colony think it would help in the search :D

Hmmm...specific links to ant colony optimization (ACO)....

Links are easy to find, but most are in the form of published research papers. If you don't mind reading those, you can do a quick seach on google to find alot of them.

One of the original papers on ACO can be found here:
http://citeseer.ist.psu.edu/239263.html

I'll post the implementation you'll need for your problem in a bit. Short of time right now.

Bruteforce should be a good option here.

Then again, you can use ab, with a heuristic, so that you end up searching very very few nodes. (you expand nodes based on how well they were on the previous level. For eg. if it was a cutoff, you examine it last. If it was the best move, you examine it first, ect.)

From,
Nice coder

Yeah I'm currently trying to develope a method by which the program can take an "educated guess" as to which nodes to explore and which to not explore :) the problem is that predicting wether or not a huge score is 5-6+ moves away would be hard.