search

Sindarus / tsumegomaker

A website that challenges you with Go problems, with a Go engine written in Ruby from scratch.
1 stars 1 forks source link

This is a thread to talk about minimax optimization #22

Open Sindarus opened 8 years ago

Sindarus commented 8 years ago

We shouldn't stop the minimax after a given number of moves, we should stop when user's score get's below a given threshold. This way, I think we could cut some big minimax branches, and still have something playable : if the user's score gets below -10 for instance, they cannot say "Hey, why are you stopping the game now ? I don't understand what's wrong with my moves.". This seems to me like a really good idea right now. It is true that sometimes you have to give some stones away to kill the opponent, and thus, we have a bad score and this is still the best way to play, but we're talking about 5 points given away, maximum.

In the same way, we could say that we stop the minimax at nodes where the AI has got a score below a given threshold. That way, we can cut big branches of the minimax, and the AI still knows that those nodes suck for him. If such nodes are reached in game by the player, we can give him the victory.

For the AI, if two moves are worth the same amount of points, the IA should prefer to pass. This avoids cases where the IA would make pointless invasions.

I discussed minimax with Jon, and he mentioned the possibility to have different scoring functions for the two players. I think this could help us fix a problem that we talked about at the Bartholdi, but that I cannot remember of. It was about giving some moves infinite scores. Also, I don't understand yet what the role of alpha & beta is in the optimization, because it seems to me that there's no need to set any of theses parameters from what I've read on wikipedia, but I think we should be talking about how to choose thoses parameters

Yoz0 commented 8 years ago

Stop the minimax when the score gets under below a certain threesold -> It could work on some problems, but it could also fail on others. If the score never get under that threesold the minimax will go on. So it's interssting to add it but it won't replace the "stop after a given number of move".

AI passing over moving -> Ok, implemeted in commit 2e7209e

Two scoring function -> Wow, this is weird.... I don't understand, we're using the "true" scoring of Go, why would we use another function ? We discussed about "What if the AI try to stall to get to the maximum number of moves ?" But it doesn't seem to do that for now.

Alpha beta -> There is no parameter to choose. The best explanation I found was this.

Sindarus commented 8 years ago

Ok.

Two scoring functions : I was thinking of differences on some nodes only. For example, some nodes could have an infinite score for one player, and normal score for the other. Maybe it'll be useful in the future. Alpha beta : thanks, that's also what I found the most useful.