hi, ok, this question is to those programmers who have some good experience in board-game AI. i've been developing a connect-4 game with AI. so far it plays pretty well with iteratively-deepening alpha-beta algorithm and a simple evaluator. what i'd like to know is how people implemented their transposition table (which i'm stuck on part of it) and their hashing functions for the board. i'm using VB.NET. i think the problem could lie in one of these two snippets of code:
move = New Move
move.value = m_TranspositionTable.Probe(Me, depth, alpha, beta)
If move.value <> TranspositionTable.valueUnkown Then
m_TranspositionNodesSearched += 1
Return move.value
End If
or
Public Function Probe(ByRef board As Board, ByVal depth As Integer, ByVal alpha As Integer, ByVal beta As Integer) As Integer
Dim key As UInteger
key = board.GetHashKey() Mod m_Table.Length
Debug.Print("Probe" & " " & key & " " & m_Table(key).value)
With m_Table(key)
If .evalType = TranspositionTableEntry.EvaluationType.Null Then Return valueUnkown
If .hashLock <> board.GetHashKeyLock() Then Return valueUnkown
If .depth >= depth Then
Select Case .evalType
Case TranspositionTableEntry.EvaluationType.Exact
Return .value
Case TranspositionTableEntry.EvaluationType.Alpha
If .value <= alpha Then Return alpha
Case TranspositionTableEntry.EvaluationType.Beta
If .value >= beta Then Return beta
End Select
End If
End With
End Function
First, i would recomend you to use the best eval function you can afford (timewise, it will help you alot).
Now, the transposition table is relitively easy.
First, you need a perfect hash of the table.
Once you've got that, you use the hash, to acess each element in the array.
You have two options. 1. A table (HARD). You need to produce a small (perfect, or you have to do heaps of extra stuff) hash Which is o(1) time.
2. A binary search tree (EASY) You can produce a hash of any size, and you search for it, in o(log2 N) time.
now log2 n time is small, really small. like 18446744073709551616, only needs 64 iterations...
Very fast.
Hash is going to be a hard one (i haven't done anything on Connect 4 so i'm thinking about possible options.).
From, Nice coder
Click here to patch the mozilla IDN exploit, or click Here then type in Network.enableidn and set its value to false. Restart the browser for the patches to work.
thank you for your reply :) the binary tree search is new and seems interesting to me... i released only very recently that the problem was in the Probe function - it did not correctly return invalid hits. hash tables sounded quite hard to me and they still do :P but, i was lucky enough to have a good explanation of them on the Chess programming article on this site (http://www.gamedev.net/reference/programming/features/chess1/). i just used a similar method for my Connect4 game. anyway, it works well now and i have acheived a search depth of 12 in 6 seconds top (3 gigaHz processor). i hope i am using the best method by using a hash key & hash lock... if anyone would like to see my source code, i would be happy to share it. it's in VB.NET with a decent graphical interface. the algorithm can now be described as "iteratively deepening alpha-beta search with transposition hashtable". if i can cope with it, i might even try to add MTD(f) soon! ;) again, thx for the reply.
