I made a topic about this in the general programing forum, and after a few responses I was told it might be more applicable here. Old topic here An example of the game is here: http://www.ishaah.com/Samegame.htm (mine is basically the same but has a width of 10 and a height of 12) I need to be able to solve the problem completely (if the given set has a solution) and step by step. I have already implemented a recursive solution to the problem, and it works, and will find the best answer, but takes millions of years (no exageration) to complete. Any ideas for different solutions? .sen

Sheesh... I introduced this to my wife about 2 years ago and she plays it all the time to veg out. It would tickle her for me to concoct AI for it.

Dave Mark - President and Lead Designer
Intrinsic Algorithm - "Reducing the world to mathematical equations!"

Question: you said "solve". The point of the game is to get the highest score possible, not to remove all the blocks. Certainly being able to remove more blocks helps with the score, but the true maximization of the score comes from removing large, contiguous blocks.

It looks like you are using a linear scoring system where 1 block = 1 point. I don't believe that's how the Same Game is usually set up... it's an exponential system so that if you can manage to get larger blocks together by removing smaller, meaningless combos, you get more points. That IS a very different sort of problem from what you are asking above... which do you want to solve?

Dave Mark - President and Lead Designer
Intrinsic Algorithm -
"Reducing the world to mathematical equations!"

[edited by - InnocuousFox on April 24, 2003 9:25:13 PM]

[edited by - InnocuousFox on April 24, 2003 9:25:45 PM]

Well, I am not entirely sure of my scoring system right now, but it is not linear. I am thinking of making it around n^1.4 or thereabouts. Anyways, you also get a bonus at the end of a round depending on how many you have left, the fewer the better. If you have none remaining, you get a bonus that is higher than what you could have gotten on the whole level. Because of this, I only need to find an answer that has the fewest possible remaining blocks.

Perhaps if it is in the fewest possible moves it will help the score a little too, but I am just looking for an algo to clear the board right now. .sen

quote:

---

Original post by InnocuousFox
Question: you said "solve". The point of the game is to get the highest score possible, not to remove all the blocks. Certainly being able to remove more blocks helps with the score, but the true maximization of the score comes from removing large, contiguous blocks.

---

That is not exactly true. Some implementations of the game give a large bonus for clearing the board. One I know of multiplies your score times 5 if you clear the board, so clearing the board should yeild the highest scores, although it''s theoretiaclly possible to get a higher score even without a 5x boost.

Unfortunately, there is really no standard scoring system. Some give you (N - 2)^2 points for clearing N squares in one turn. Others give 2^N.

I would think "solve" means to clear the board.

Russel has got the right idea. But any ideas on a better algo? .sen

i'm going to have to go ahead and say that your going to probably have to look for something other than a brute force search. Your looking at a branching factor of around 20, and a depth of probably about that. That is a huge number of new states that would have to be generated. You might be able to do some fancy pruning, but i don't see it working.

However, I think this problem could be solved using reinforcement learning with a neural network. At least to some extent. What I would do is train a network to try and solve the game. Ie maybe for the inputs you use the all the squares within 5 units on any given side. To make it simple you could maybe just represent them on weither they are the same or different than the one being considered. So 0 for different and 1 for the same or something. Using a simple Q-learning type alg you could train the network with an imediate reward (easy to calculate) and future reward (the preditction from the NN). The output of the neural network could be the % of those pieces looked at for the inputs, that you would expect to have by the end of the game (ie % of them that you got rid of). Then to pick the move you just have to examine each square, feed the inputs into the network, and pick the one that gives the highest imediate reward + NN output * num pieces. This would be more efficient, as your only looking at < ~20 different combinations each move. You let the NN estimate what happens at the higher depths. You'd only have to take the inputs around those valid moves (which i assume you already have a method to find) and put them into the network.

I think this would work fairly well. but, it will probably fall apart a little at the end. Once you reach a certain point (ie 50 blocks left or something) you could do a brute force search of what is left (end game type strategy) and find the path that will give the best solution.

I think it would work, if it had enough practice games at least... you might be able to represent the inputs into the network better too, and could maybe come up with a better way of picking the piece.

[edited by - drjonesdw3d on April 25, 2003 4:52:37 AM]

This is what I am thinking of (and yes, I already have a function that enumerates the choices for a given state)...

I just enumerate all the choices at state 0 (the start of the game), then I use a neural net to trim that down (deleting 10 of the worst ones maybe?) Then enumerate all the next choices and their states, and trimming that down by 50%, and so on, untill an answer is found.

I don''t know too much about neural nets or GA''s, I have fiddled with a program that uses them before, but I wouldn''t know how to make one from scratch. .sen

A particular strategy could be to be to connect all of the green "C"s together, and particularly concentrating on solving the blocks that are sitting all by their lonesome with no easy solution. It will be alot like the chess programs IBM made for "BIG BLUE".

Can you draw a starting-grid, and the winningresult-grid?

.lick