Java Programming Forums - The Java Community - Algorithms & Recursion

Killer Moves Heuristic for Alpha-Beta (Connect 4), need some technical help

patishi — Sat, 01 Jun 2013 15:03:18 GMT

Hi all. first of all let me apologize in advance for this rather noob question and if this is not the right sub-forum please let me know and transfer the post.
I am a java beginner/intermediate,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! below is my Minimax function

Code java:

	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;
        	reply = chooseMove(!side,board,alpha,beta,depth+1,maxDepth);
        	board[move.intValue()] = 0;
			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;
	}

make own OCR

Suhail Tamboli — Fri, 31 May 2013 05:09:02 GMT

Hi friends,

I am Suhail and I got college project to make on OCR so please any one can help me to know how to write code for OCR in java .

I want to know the logic to recognize character from image....

Waveform Generator?

sci4me — Sun, 26 May 2013 06:30:46 GMT

Hey guys. So, I am wondering.. I need to implement this interface for some of the common waveforms such as sine:

Code :

public interface SignalFunction
{
	public double f(int freq, int time);
}

And.. im not exactly sure how... I mean for sine, would it simply be this:

Code :

public double f(int freq, int time)
{
        return Math.sin(time);
}

?
As for sawtooth, triangle and square, im not sure. If anyone can help me implement these, I would really appreciate it. Thanks!

EDIT:

okay... so... I am currently working on making a triangle wave. I have this:

Code :

Math.abs((((2 * t) / Math.PI - 1) % 4) - 2) - 1

It almost works... but its not QUITE a triangle.... what am I doing wrong?

[SOLVED] A linearithmic (at most) complexity algorithm to generate Pythagorean triples

angstrem — Sat, 25 May 2013 18:26:02 GMT

I've been working on ProjectEuler's Problem 75 for about 4 days already, and it completely burns my brain. It's easy to generate Pythagorean triples with Euler's or Dickson's methods, but they're all of quadratic complexity, not something you want to use when aiming for ~million triples. I just can't figure any better method. So, can anybody suggest me an algorithm of at most linearithmic complexity to generate all the Pythagorean triples?