It is currently Tue Apr 24, 2018 12:52 pm Advanced search

Minimax algorithm

Share and discuss ideas for your entries here.

Minimax algorithm

Postby brikbrik » Sun Feb 07, 2010 8:27 pm

Hi all !

I explain the strategy my bot is using at http://www.sifflez.org/misc/tronbot.
It is a minimax with iterative deepening and alpha-beta pruning which uses flood-fill
to compute the space available for each player in its evaluation function.
brikbrik
Cadet
 
Posts: 1
Joined: Sun Feb 07, 2010 8:20 pm

Re: Minimax algorithm

Postby nneonneo » Sun Feb 07, 2010 10:47 pm

This is a very nice guide! I wrote the strategy page on the main site. Do you mind if I link to your guide?
nneonneo
Captain
 
Posts: 26
Joined: Sun Jan 31, 2010 5:39 am

Re: Minimax algorithm

Postby Experiment Garden » Tue Feb 09, 2010 4:21 am

I love the guide but I was wondering if you could go into a tad more detail about exactly how you generate numeric scores for a particular game possibility in the tree.

I understand that this may be the critical cutting edge part of your bot so I understand if you don't want to tell us, but I must still wonder.
Experiment Garden
Cadet
 
Posts: 9
Joined: Fri Feb 05, 2010 5:26 pm

Re: Minimax algorithm

Postby shettynamit » Tue Feb 09, 2010 6:49 pm

If someone could please give some basic idea about the evaluation function (the values, how to arrive at the precise values)... it would be highly appreciated.
Thanks a ton in advance :)
shettynamit
Cadet
 
Posts: 2
Joined: Tue Feb 09, 2010 6:44 pm

Re: Minimax algorithm

Postby nuvw » Tue Feb 09, 2010 11:01 pm

That's obviously not an easy question. And there is no right answer to it.

I think the best thing you could do is to ask yourself how you would play. Would you immediately approach the opponent, or rather stay away from him? Would you stay at the border of the map or go to its center? When you have come up with something, give it a try. There is almost no way to tell in advance, whether it will make your bot stronger or it will make him commit suicide in the first couple of moves.

Once the players are separated the evaluation function is actually "quite clear", the one with the longer path in its territory wins. Unfortunately it's not that easy to efficiently calculate the longest path, so you will have to find some way of getting a good approximation. Counting all reachable squares would be a start here.
nuvw
Cadet
 
Posts: 5
Joined: Sat Feb 06, 2010 11:05 pm


Return to Strategy

Who is online

Users browsing this forum: No registered users and 1 guest

cron