Applying go methods to other games

Implementing and improving the AlphaZero algorithm
Posts: 2
Joined: Tue May 13, 2008 9:26 am

Re: Applying go methods to other games

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

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

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.