File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
The moose likes Game Development and the fly likes History Heuristics in game Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Game Development
Bookmark "History Heuristics in game" Watch "History Heuristics in game" New topic

History Heuristics in game

Kabir Shah
Ranch Hand

Joined: Aug 04, 2009
Posts: 125
I want to add history heuristics for my game of connect four.

Till now I have programed fully functional connect-4 ai implementing negamax algorithm and basic evaluation function.

Later on added alpha beta pruning to it so that the search time would be low(It does work, it drastically reduces).

Now to optimize it further, I would like to add history heuristics to it and later on transposition table.
Here is the code for negamax.

The above code is for negamax+abp

The sort method sorts all the indexes of array in descending order(Maximum value will be fed first to negamax_ab, this is called as history heuristics).
the array curr_val[] is global parameter which has length of 7.It stores all the values returned from the negamax_ab().
These values are then stored in array called as vals[] which has same size as that of possible move.

Even by this, The time required to search is the same without history heuristics.
Mich Robinson
Ranch Hand

Joined: Jun 28, 2009
Posts: 260
I'm not sure what your question is?

If it's "how do I add this feature" then just:
  • Search for the best move at a low search depth.
  • Then make the search deeper
  • Try the above move first before looking at other moves.
  • The alpha beta pruning should prune more of the tree this way
  • If you order all the moves by their score then you could try each in turn to further optimise pruning.

  • Mike

    Arcade : Alien Swarm
    Board : Chess - Checkers - Connect 4 - Othello
    I agree. Here's the link:
    subject: History Heuristics in game
    It's not a secret anymore!