Greetings I've done small program playing noughts and crosses (or gomoku). Since it's still slow, I've decided to implement transposition table to speed it up a bit. I made function calculating board hash value (the result is 57-char. string), function returning boolean if same game state was evaluated before (searching linked list for identical hash) and implemented it into minimax. When searching the tree, I make one linked list of all board instances for each depth. After search, I have linked list of depths pointing to linked list of game states and their hash values. I think this is right. But as tree search continues, algorithm is slowing down. It's because the size of linked lists is rapidly growing and searching for identical hash values takes much time. Please help me to solve this. I know there should be constant time to retrieve hash from table but how? I always have to start searching from beginning of linked list. Thank You!

Stop what your doing!!

Make sure that you are using Alphabeta, before you try anything else! (it will give you the biggest speed boost, ever.).

Linked list! Thats an o(n) search!

you either use a hash table (which is hardish), or you could use a vector.

You make anarray (or vector, or ?) with a few million/ten million elements.

In each one, you put the Hash, and its value, IN order.

You then search it, using a binary search (in o(log2 n) time).

Why is this importaint?

Let me put it this way, it would take 32 iterations, to find one item out of 4 billion, in the array. on average.
Or, it would take 64 iterateions, to ifnd one item out of 18,446,744,073,709,551,616.
Thats Eighteen quintrillion, Four hundred fourty six Quadrillion, Seven hundred fourty-four trillion, Seventy three billion, Seven hundred nine million, Five hundred fifty one thousand, Six hundred sixteen.

So, its fast. Very, fast
Adding to it, takes the same amount of time as reading from it, ie. o(log2 n).

Not as fast as a hash table, but fast enough. (for the space savings... Just make sure that your has doesn't collide that often)

Now, how to make an efficient hash function? (which doesn't collide?)

there are a total of 32 squares which are occupiable by any piece.
There are Five states, any square could be in. (Empty, Red man, black man, red king, black king.) Thats a bit over 2 bits per state.

There are also 24 pieces (12 red, 12 black).
There are only 48 possible pieces (12 red men, 12 black men, 12 red kings, 12 black kings).


Now, 4 bits (16), can hold 3 squares worth.
There are 32 squares, so we need 40 bits. Thats a little two big.

Or, 5 bits (32) can hold 6 squares.
There are 32 squares, so we need 26 bits.

Which would fit handsomly in a 32 bit long.

Its up to you, how to make the hash function. But there are two things it needs, Speed and the ability to make a very small hash. (your going to need millions of hashes)

(i'm not particularly good at the maths of it, if theres any mistakes, let me know, ok?)

I'll probably add to it, after the storm has past.
From,
Nice coder.

Ok, hash tables, and binary search trees.

With a hash table, you basically have a hash function:

int hash(int board);

Which returns a number.

You then go

Index = hash(board) % hashtablesize;

To find the index of the element to find.

so, what you would do, is you would have an array of pointers, which point to the records. (for eg, The value of the board, or an array of board with there corresponding values... (when you have a collision))

// This is C/C++ish, not actual codeElement* hashtable[]int Hashsizeif (hashtable[hash(board) % hashtablesize]) {    //That spot in the table is occupied}hashtable[hash(board) % hashtablesize] = nrecord //Set the hash table, to the value of nrecord

Hash tables, just in case i haven't explained it well enough

I'm not sure that you'd really need the hash table... If you need something simpler, and smaller (memorywise), and that is just a little bit slower.

You could use a binary search.

Its sortof like a linked list, only its a bit different, and a lot faster (o(log2 n) rahter then o(n)).

Its hard to explain (tho its dead simple to make), so i'll let my friend google help.
Binary search trees
Google for bst's

Hth.
From,
Nice coder

Thx for reply.

I have alpha-beta of course.
I've even done best-first.

Yes, I told you the program is still slow. Maybe it's not true but I want it faster! :). Transposition tables was real challenge and there are many reoccurent game states so why evaluate them again and again.

I'm worse in math than you can imagine -- maybe there is problem too :).

Now, I'am going to decide what to do.
I'll let u know.

Thx again,
ProblemSolver

Ok,

I'll remake linked lists to binary trees or red/black trees,
leaving my hf() intact. This should bit result in slower algorithm
but there will be no collisions -- no possible mistakes.

Thanks for your advice.

ProblemSolver

Binary trees are fine. and fast. Very fast. (as i've said before).

Checkers, checkers, checkers...

Just make sure your evalueate jumps ahead of all else.

Do you have a positional evaluation function, in addition to just material?
If you don't, then it'd give you a nice little speedup.

Also, how are you sorting your nodes? Quicksort? Mergesort? Bubblesort?

From,
Nice coder