• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

History Heuristics in game

 
Kabir Shah
Ranch Hand
Posts: 125
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 260
1
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
     
    It is sorta covered in the JavaRanch Style Guide.
    • Post Reply
    • Bookmark Topic Watch Topic
    • New Topic