Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (477)
Games in Android Showcase (107)
games submitted by our members
Games in WIP (535)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Killer Moves Heuristic (Connect 4)  (Read 443 times)
0 Members and 1 Guest are viewing this topic.
Offline patishi

Junior Newbie





« Posted 2013-06-01 10:57:56 »

Hi all. first of all let me apologize in advance for this rather noob question,i am a java beginner,but very facinated with AI programming and programming in general. I am developing my own connect 4 android app, and i am using a standart MiniMax algorithm with Alpha-Beta for the search. But the problem is that in depth >9 the search just takes too much time. so,searching for a easy to implement anhancement for my Alpha-Beta i came across the "Killer Move" Heuristic which i pretty much got the idea of it. But i need some help to implement it in my code.

This is my MiniMax function, the "Best" Object holds a move(int) and also a score for that move (also an int).
And i know that i need to catch the move that causes a cut-off (when alpha>=beta) and use it as a killer move,but i just can't figure out how to do it exactly. do i need to make it for each ply?  where exactly should i initialize the killerMove variable inside this function? 
please Don't think i am lazy, i DID searched the net and couldn't find code examples for this,only theoretical background. and i really would like to implement it in my code and learn another thing and increase my experience.Even if i can somehow manage to do it by myself, it is important to me that i am doing it right.
 Any help would be appreciated! thanks  below is my Minimax function

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
   public Best chooseMove(boolean side,int[]board,int alpha,int beta,int depth,int maxDepth){
      Best myBest = new Best();
      Best reply;
      int num;
      if(Board.checkGameOver(board)||depth==maxDepth){
         myBest.setScore(returnPositionScore(board));
         return myBest;
      }
      if(side){
         myBest.setScore(alpha);
         num = numberOfEngine;
      }
      else{
         myBest.setScore(beta);
         num = numberOfOpponent;
      }
        ArrayList<Integer> availableMoves = new ArrayList<Integer>(searchAvailableMoves(board));
     
        for(Integer move:availableMoves){
           board[move.intValue()] = num; //Make the move
          reply = chooseMove(!side,board,alpha,beta,depth+1,maxDepth); //Recursive call with the new board position
          board[move.intValue()] = 0; //Undo the move
        if(side&&reply.getScore()>myBest.getScore()){
            myBest.setMove(move);
            myBest.setScore(reply.getScore());
            alpha = reply.getScore();
         }
         else if(!side&&reply.getScore()<myBest.getScore()){
            myBest.setMove(move);
            myBest.setScore(reply.getScore());
            beta = reply.getScore();
         }
         if(alpha>=beta){
            return myBest;
         }
        }
        return myBest;
   }
Offline ReBirth
« Reply #1 - Posted 2013-06-01 14:33:35 »

Although I have created an ultimate* Connect4 back in college but sorry I can't help, the code is too unclear and hard to understand. Narrow down the problem?

*) the AI is so damn good that it's hard to win.

Offline patishi

Junior Newbie





« Reply #2 - Posted 2013-06-01 16:03:41 »

sorry if my code is a little messy, but generally i think that this is a rather simple Minimax/ alpha-beta function..I can't write this clearer than the way it is already written. (by the way,this code was originally written by a berkley professor).   All i want to achieve is the implementation of the "Killer move" hueristic algorithm to further maximize the alpha beta prunning.  
I was reading about this algorithm and it seems very simple, the idea is to re-order the moves so the best move(the killer move) will be played first, and will cause a alpha-beta cut off (which will speed up the search).  
But i just can't figure out how exactly should i implement it in my code.    
can i ask what exactly you don't understand in the above written function?
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline ReBirth
« Reply #3 - Posted 2013-06-01 16:18:09 »

Hmm you need to ask someone who understand that Minimax algorithm. Maybe other members can help.

Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

pw (37 views)
2014-07-24 01:59:36

Riven (38 views)
2014-07-23 21:16:32

Riven (26 views)
2014-07-23 21:07:15

Riven (28 views)
2014-07-23 20:56:16

ctomni231 (58 views)
2014-07-18 06:55:21

Zero Volt (49 views)
2014-07-17 23:47:54

danieldean (41 views)
2014-07-17 23:41:23

MustardPeter (43 views)
2014-07-16 23:30:00

Cero (59 views)
2014-07-16 00:42:17

Riven (56 views)
2014-07-14 18:02:53
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!