Win a copy of The Way of the Web Tester: A Beginner's Guide to Automating Tests this week in the Testing forum!

MiniMax Logic Issue

Aj Seth
Greenhorn
Posts: 3
So I am working on MiniMax for Connect4. I have written the code after referring to various posts and as far as I know the basic code structure is good. The issue is that the AI does not block the winning moves of human player all the time. I think the issue is with the heuristic of board valuation. I have used various methods and it does not work. So I need help !

Take a look at the current board below. Here 1 = human , 2 = AI and its AI's turn now.

Now ideally AI should chose 2,2 position to block human win but it goes for (0,6). The output is attached with the question.

Here is a basic flow of code

The move value is calculated as per following logic
1. Count consecutive pieces of both human and AI at the node.
2. Move Value += n4*4^4 + n3*4^3 + n2*4^2(Here n4 = number of 4 consecutive coins for AI and n3 = count of 3s and so on)
3. Move Value -= ( n4*4^4 + n3*4^3 + n2*4^2 ) (here N4 is for human).

Aj Seth
Greenhorn
Posts: 3
Apologies for a huge question.

Output -> >>>>Current maxMove||Player :2|MoveX :4|MoveY :0|Move Value : -96|Depth : 2
>>>>>>Current minMove||Player :1|MoveX :3|MoveY :0|Move Value : -96|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :4|MoveY :1|Move Value : -128|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :2|MoveY :2|Move Value : -544|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :4|MoveY :3|Move Value : -112|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :5|MoveY :4|Move Value : -96|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :3|MoveY :5|Move Value : -96|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :0|MoveY :6|Move Value : -352|Depth : 1

minMove Return||Player :1|MoveX :3|MoveY :5|Move Value : -96|Depth 1

>>>>Current maxMove||Player :2|MoveX :4|MoveY :1|Move Value : -96|Depth : 2
>>>>>>Current minMove||Player :1|MoveX :4|MoveY :0|Move Value : -112|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :3|MoveY :1|Move Value : -112|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :2|MoveY :2|Move Value : -544|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :4|MoveY :3|Move Value : -112|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :5|MoveY :4|Move Value : -96|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :3|MoveY :5|Move Value : -96|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :0|MoveY :6|Move Value : -352|Depth : 1

minMove Return||Player :1|MoveX :3|MoveY :5|Move Value : -96|Depth 1

>>>>Current maxMove||Player :2|MoveX :2|MoveY :2|Move Value : -96|Depth : 2
>>>>>>Current minMove||Player :1|MoveX :4|MoveY :0|Move Value : -112|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :4|MoveY :1|Move Value : -128|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :1|MoveY :2|Move Value : -160|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :4|MoveY :3|Move Value : -112|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :5|MoveY :4|Move Value : -96|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :3|MoveY :5|Move Value : -96|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :0|MoveY :6|Move Value : -352|Depth : 1

minMove Return||Player :1|MoveX :3|MoveY :5|Move Value : -96|Depth 1

>>>>Current maxMove||Player :2|MoveX :4|MoveY :3|Move Value : -64|Depth : 2
>>>>>>Current minMove||Player :1|MoveX :4|MoveY :0|Move Value : -80|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :4|MoveY :1|Move Value : -96|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :2|MoveY :2|Move Value : -512|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :3|MoveY :3|Move Value : -80|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :5|MoveY :4|Move Value : -64|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :3|MoveY :5|Move Value : -64|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :0|MoveY :6|Move Value : -320|Depth : 1

minMove Return||Player :1|MoveX :3|MoveY :5|Move Value : -64|Depth 1

>>>>Current maxMove||Player :2|MoveX :5|MoveY :4|Move Value : -80|Depth : 2
>>>>>>Current minMove||Player :1|MoveX :4|MoveY :0|Move Value : -96|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :4|MoveY :1|Move Value : -112|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :2|MoveY :2|Move Value : -528|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :4|MoveY :3|Move Value : -96|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :4|MoveY :4|Move Value : -80|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :3|MoveY :5|Move Value : -80|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :0|MoveY :6|Move Value : -336|Depth : 1

minMove Return||Player :1|MoveX :3|MoveY :5|Move Value : -80|Depth 1

>>>>Current maxMove||Player :2|MoveX :3|MoveY :5|Move Value : 16|Depth : 2
>>>>>>Current minMove||Player :1|MoveX :4|MoveY :0|Move Value : 0|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :4|MoveY :1|Move Value : -16|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :2|MoveY :2|Move Value : -432|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :4|MoveY :3|Move Value : 0|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :5|MoveY :4|Move Value : 16|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :2|MoveY :5|Move Value : -256|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :0|MoveY :6|Move Value : -240|Depth : 1

minMove Return||Player :1|MoveX :5|MoveY :4|Move Value : 16|Depth 1

>>>>Current maxMove||Player :2|MoveX :0|MoveY :6|Move Value : -96|Depth : 2
>>>>>>Current minMove||Player :1|MoveX :4|MoveY :0|Move Value : -112|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :4|MoveY :1|Move Value : -128|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :2|MoveY :2|Move Value : -544|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :4|MoveY :3|Move Value : -112|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :5|MoveY :4|Move Value : -96|Depth : 1

>>>>>>Current minMove||Player :1|MoveX :3|MoveY :5|Move Value : -96|Depth : 1

minMove Return||Player :1|MoveX :3|MoveY :5|Move Value : -96|Depth 1

maxMove Return||Player :2|MoveX :0|MoveY :6|Move Value : -96|Depth 2
MovePlayer: 2|MoveX: 0|MoveY: 6|Board: 55
0 0 0 0 0 0 2

0 0 0 0 0 0 2

0 0 0 0 0 0 1

0 0 1 0 0 0 2

0 0 1 0 0 2 2

1 1 1 2 0 1 2

Les Morgan
Rancher
Posts: 709
17
Seth,

There are a few things I need to ask before I start looking over your code. You want the AI to truncate the options, block, the human, but how many generations ahead do you let the AI go: are you doing an A* from the current board configuration and having the AI choose the most beneficial path or do you have a limited number of moves for your horizon?

Greg Pata
Ranch Hand
Posts: 31
Hi Seth,
I think you've already solved the problem.
Anyway there is a solution here.
Then one can try to debug the proposed evaluateBoard method (the evaluation for certain grids and the associated symetric grids is not the same).
Finally, one can try to find a better way to evaluate the board by beating the AI. This point is not straightforward.
Cheers,