Applying go methods to other games

Monte Carlo Tree Search
m.schadd
Posts: 2
Joined: Tue May 13, 2008 9:26 am

Re: Applying go methods to other games

Post by m.schadd » Tue May 13, 2008 9:38 am

spurious_ai wrote:I still have some adjustments to my program and believe I can find a higher score. The biggest problem is the 2 block move. Under the scoring used for this version of SameGame, (n-2)*(n-2), a 2 block move scores 0 points.

Could the 0 point move cause a problem in their MC implementation? Should have I been able to beat their score?
What is the scoring rule you used for achieving your scores now? Is it (n-2)^2 ? If so, then congratulations on a higher score then my program.

Yes, it is true, my program clears the complete board on all the 20 positions, so the penalty at the end is indifferent.

About the 0 score move, I do not see why this move forms a problem in my implementation. The program regularly uses these moves to form larger groups. The big problem with my implementation, and probably the biggest point of improvement is the random playout strategy. As you can see in my paper, I choose the color with the most blocks on the board (One position nr.1 red) and do not play it at all in my random games until not possible otherwise. Like this large groups are formed automatically. The problem is now, that before the big group is removed, a lot of unnecessary moves are played, just to avoid playing the red group. This is where points get lost.

I would be interested in your method that you use. Do you have any information for me on that? Thx.

spurious_ai
Posts: 34
Joined: Fri Mar 28, 2008 8:15 pm

Re: Applying go methods to other games

Post by spurious_ai » Tue May 13, 2008 2:01 pm

I don't know much about depth searching. All my work has been in breadth searching. In my algorithm, 0 point moves cause some problems. I did not mean to imply that it caused a problem with your program, it was a question. I don't have a formal education so I understand very little when I look at research papers.

My algorithm is descibed in the Numbrosia thread. It is basically a greedy solution. It uses a simple static evaluation, so solutions that have moves that reduce the evaluation can fail. It can find a good solution in a short amount of time. The program spent about 20 minutes on each solution. I need to sort out a few more problems and I will rerun all the puzzles with the 2 hour metric.

spurious_ai
Posts: 34
Joined: Fri Mar 28, 2008 8:15 pm

Re: Applying go methods to other games

Post by spurious_ai » Mon May 19, 2008 8:38 pm

From their paper:
Since no good evaluation function has been found yet, SameGame presents
a new challenge for the puzzle research.
There is a simple evaluation that works quite well. More complex evaluations can help solve the puzzle more quicky when the beam size is low, but with a large beam size, the simple evaluation is all that is needed.
m.schadd wrote:
As you can see in my paper, I choose the color with the most blocks on the board (One position nr.1 red) and do not play it at all in my random games until not possible otherwise. Like this large groups are formed automatically. The problem is now, that before the big group is removed, a lot of unnecessary moves are played, just to avoid playing the red group. This is where points get lost.
Many times the higher scoring solution involves breaking the color with the largest count into 2 or more groups, allowing a large group to be formed from another color. Two or three medium size groups can beat the one large group.

I am currently at 82604, 8606 points beyond your solutions. I believe there are thousands of points more in the optimal solutions.

Back to the topic.

Move generation is expensive for SameGame, so playing random games will take time. Move generation for Go is probably not as simple as "find an empty point to place a stone", but it is much faster.

Go methods may work in other games but might not be practical because of time constraints. But before considering time, the method must produce a better solution.
Last edited by spurious_ai on Mon Jun 09, 2008 8:44 pm, edited 1 time in total.

Post Reply