Ok, I implemented History heuristics with iterative deepening and it further delayed but quiet a measurable extent.
I think that the major cause of this is due to poor evaluation function (Search for WIN-LOSS only).
Can anyone guide me here, how to speed up, I want to keep knowledge as low as possible(I know this is bad, but I want to prune the tree on a higher extent by forcing moves).
Is there any extension of algorithm which can speed up.

I have implemented killer move heuristics(works great), with hashtables.
I also try the move from hashtables first, but then too the performance doesnt really speed up.

Can anyone shine some light on my observation and query.

Thanks.

Writing a strong program that only uses win-draw-loss is hard. Consider the following situation:
_ _ _ _ _ _ _
_ _ _ _ _ _ _
_ _ _ _ _ _ _
_ _ X 1 Y Z _
_ _ 1 2 1 _ _
_ _ 2 1 2 _ _
It is 2's turn to move, and if it plays at X, player 1 can play at Y, which leads to a straight-forward victory (fill up the rightmost column, stay out of trouble elsewhere and win at Z). Unless you incorporate some knowledge in your program, it will have to search to depth 30 or so before it realizes it. Because I have some knowledge of the game, I can see it with essentially no search.

John Tromp wrote a connect-4 program that can search the whole tree from that position in at most a few seconds. His program Fhourstones searches the starting position in about 5 minutes on my desktop machine. He even has a Java applet in this page that plays perfectly (using a database for positions after 8 moves). So what you are trying to do is certainly possible, but you need to be a very good programmer to do it.

John insists that some variant of history heuristic is what allows his programs to be so fast. The code to Fhourstones is available, so perhaps you can just read it to find what the exact details, but his description was basically having one byte per square on the board, which are used to sort the moves (descending). They are initially all 0, and if a beta-cut happens after exploring the third child of a node, the first two children get their scores reduced by one and the score of the third child is increased by 2 (so the sum of all the scores is always 0). The score is capped to avoid overflow (and to stay nimble and adapt to changing circumstances when exploring different parts of the tree). I imagine he keeps a separate table for each player.

@alvaro: Thanks for the reply, and a good example which used zugswang to force up a win. Is there a method by which I can find which player controls the zugswang.
I tried to read Victor Allis thesis and the rules which are described in them can be summed up in bitboard fashion pretty decently.
However I fail to understand how to determine which player holds the zugswang.

I also read the explanation given by John Tromp, he has used some heavy stuff.
Will try to implement the logic.

Another question off the topic, how can I be a better programmer? I am coding from past 2 years and now I think I am not growing.
How can I be better. Are there any assignments? Some way of logic building or some classes/books on algorithms I should read? Or is this a phase in every programmers life?

Thanks.

This book on Connect 4 is a great place to learn about strategy for this game, which is primarily about what you call "holding the zugswang".

It's not a short thing to explain, although the very basic idea is that, if you imagine the whole board fills up except the square below the threat and above, you can determine whose turn it will be at that point by looking at the parity of the number of empty squares left. So, if we label top row as even, player 1 wins with a threat on an odd row and player 2 wins with a threat on an even row, if there is nothing else going on on the board. Player 2 can win with 2 odd threats. Now an interesting observation is that an odd threat of player 1 beats any number of even threats of player 2. The exact classification of columns and how they combine is covered in the book.