Jump to content

  • Log In with Google      Sign In   
  • Create Account


minimax with alpha beta pruning implementation stuck.


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
28 replies to this topic

#21 whitenose   Members   -  Reputation: 124

Like
0Likes
Like

Posted 15 October 2012 - 12:01 PM

@alvaro

...
EDIT: Wait, why are you passing a sign around?


Sign value is: +1 or -1 (it alternates between MAX = +1 and MIN = -1 teams).
It's not correct ?

Sponsor:

#22 Álvaro   Crossbones+   -  Reputation: 11906

Like
1Likes
Like

Posted 15 October 2012 - 12:09 PM

What do you do with it? I don't see it in your code...

The whole point of NegaMax is that it makes all the nodes max nodes, with the resulting code being simpler.

EDIT: Oh, I see you are passing it to your evaluation function. One typically uses whose turn it is, which is part of the board class.

Edited by alvaro, 15 October 2012 - 12:11 PM.


#23 whitenose   Members   -  Reputation: 124

Like
0Likes
Like

Posted 15 October 2012 - 12:14 PM

yes, that's correct.
thanks for all the help !
i really appreciate that.

#24 whitenose   Members   -  Reputation: 124

Like
0Likes
Like

Posted 21 October 2012 - 09:25 AM

Hello,
I'm sorry i keep coming back to this subject, but i have some issues wich i help you can give me an answer.
I have this EvalFunction :


[source lang="java"] public int evaluateBoard(int sign) // -1 = "computer" and +1 = "human" { int total = 0; int computer_closedmills = this.checkMills(-1); // count how many closed mills AI has (3 tokens in a row/column). int computer_openmills = this.checkFormers(-1); // count how many 2 in a row/column tokens AI has. int computer_blockers = this.checkBlockers(-1); // count if one AI token -> blocks 2 player's tokens int computer_tokensleft = this.checkTokens(-1); // count how many tokens AI has. int computer_openspaces = this.checkOpenSpaces(-1); // count how many move possibilities AI has (in current board) int player_closedmills = this.checkMills(1); // count how many mills "human" has int player_openmills = this.checkFormers(1); // count how many 2 in a row/column "human" has. int player_blockers = this.checkBlockers(1); // etc. int player_tokensleft = this.checkTokens(1); int player_openspaces = this.checkOpenSpaces(1); // compute total score total -= ((computer_closedmills * 20)+ (computer_openmills * 40) + (computer_blockers * 30) + (computer_tokensleft * 10) + (computer_openspaces*5)); total += ((player_closedmills * 20) + (player_openmills * 40) + (player_blockers * 30) + (player_tokensleft * 10) + (player_openspaces*5)); if(sign==-1) return total; else return -total; }[/source]

Ok, now i have this situation as you can see below represented in this Picture :

http://imageshack.us...notworking.jpg/


Note that red tokens represent "computer".
Instead of moving token 22 to position 19 (wich will form a new mill) , my evalFunction() makes another decision
and moves something let's say like token 21 to position 9 , or 18 to position 10.

Can you help me improve my eval function so that token 22 moves to 19 ?
( so that mill 21-22-23 breaks and token 22 forms a new mill on 18-19-20)

thanks !

Edited by whitenose, 21 October 2012 - 09:48 AM.


#25 Álvaro   Crossbones+   -  Reputation: 11906

Like
0Likes
Like

Posted 21 October 2012 - 09:33 AM

Why are you not using `sign' in your evaluation function?

#26 whitenose   Members   -  Reputation: 124

Like
0Likes
Like

Posted 21 October 2012 - 09:48 AM

@alvaro : correction made to code.(sorry)

Edited by whitenose, 21 October 2012 - 09:48 AM.


#27 Álvaro   Crossbones+   -  Reputation: 11906

Like
0Likes
Like

Posted 21 October 2012 - 11:31 AM

It looks to me like you got the sign wrong. But you should learn how to debug your code. That position seems to be solvable with a depth-1 search, and that should be relatively easy to debug.

#28 whitenose   Members   -  Reputation: 124

Like
0Likes
Like

Posted 21 October 2012 - 12:32 PM

It looks to me like you got the sign wrong. But you should learn how to debug your code. That position seems to be solvable with a depth-1 search, and that should be relatively easy to debug.


What do you mean by wrong sign ? Where ?
For both players ("computer" or "human") the function returns a positive score, i.e. everybody is trying to maximize score, right?

You're saying that at depth=1 , the function should return best move (score) ? If so, i can confirm that (it returns biggest score for current player) !
Please help .

Edited by whitenose, 21 October 2012 - 12:34 PM.


#29 Álvaro   Crossbones+   -  Reputation: 11906

Like
0Likes
Like

Posted 21 October 2012 - 01:20 PM

This looks like the wrong sign:
if(sign==-1) return total;
    else return -total;

But perhaps I didn't understand your sign convention.

I am not sure how to help further. You need to find a situation where the program reproducibly does the wrong thing, then carefully analyze what the program is doing, probably with the help of a debugger or perhaps just by adding a bunch of print statements to your program. Try to figure out where the program is doing something different than what you expected.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS