Collecting the pv in Search

[kbhearn]

Hi Edsel,

1) Because I'm done with the TTEntry, so it has to be deleted or else it's a memory leak. I just realized, though, that if I call delete on it and then ask for a member, I'm going to get undefined behavior. Maybe I should use:

Code: Select all

if(tt->depth > depth)
         {
            int score = tt->score;
            delete tt;
            return score;
         } 

It's better C++, anyway.

generally you want to avoid allocating with new as much as possible anyways. in addition to sven's suggest of returning the real pointer to the entry in the table which wouldn't need a delete, two other coherent options:

- return a copy of the structure itself instead of a pointer if you want a copy and not the raw entry. the optimising compiler will handle making sure it's not copied twice so long as you use normal constructs (i.e. if you create a local variable to contain the copy in your probe function and always return that local variable the compiler will switch that local variable with the variable that is to receive the return value)
- create a local TTEntry variable tt in your search and pass it in as a parameter to your probe either as a reference or pointer. Pointer is syntactically clearer at the point where you call the function that what you're passing in may be changed.

In addition to wanting to avoid new whenever possible inside the inner loop of your program, separating the responsibility for new and delete into different places is dangerous as it becomes easy to forget one of the deletes or delete something too soon if you start using it from multiple places.

[elpapa]

Another thing. The lines after the move loop:

Code: Select all

NodeType node = Alpha;
TT.save(depth, move.Score, move, node, Get_Current_Hash_Key());

will erroneously overwrite any best move and exact score you may have found earlier within the loop.

Edit: Unless you somehow avoid that inside TT.Store() of course.

[theturk1234]

Ok, first of all, thank all of you for taking the time to review the code!
I heard many great suggestions, hoping to try all of them!
Here are the implementations of the TT.save() and TT.probe():

Code: Select all

TTEntry * TranspositionTable::probe(const Bitboard key1)
{
	int index = key1 % 100000;
	if(TT.table[index].key == key1)
	return &table[index];
	else
	return NULL;
}
void TranspositionTable::save(int depth1, int score1, Move best1, NodeType n, Bitboard hashkey)
{
	int index = hashkey % 100000;
	if&#40;TT.table&#91;index&#93;.depth < depth1&#41;
	&#123;
		TTEntry tt;
		tt.depth = depth1;
		tt.score = score1;
		tt.best = best1;
		tt.key = hashkey;
		tt.nodetype = n;
		TT.table&#91;index&#93; = tt;
	&#125;
&#125;

Are there any outstanding problems with these?
David Cimbalista

[theturk1234]

I just thought of it: I shouldn't be deleting the TTEntry, just like you said. That was dumb. I just wasted a lot of searching power.

[Sven]

I just thought of it: I shouldn't be deleting the TTEntry, just like you said. That was dumb. I just wasted a lot of searching power.

I see no "new" in the probe() method so you must not delete the pointer that was formerly returned by probe(). Actually it is the address of a C++ array element which simply can't be deleted.

In the implementation of probe() and save(), sometimes you use the expression "TT.table[index]" and sometimes only "table[index]", what is the difference? What is "TT" in this case?

Your hash table seems to be extraordinary small, only 100000 entries, is that intended? A TTEntry seems to hold about 24 bytes (3 integers, 1 64-bit hashkey, and a move), maybe 32 bytes (depending on the size of a move), so that would be roughly 3 MB only. Most people today use 256 MB, 512 MB, 1 GB, ... which will usually lead to a higher number of TT hits.

Only replacing a TT entry if the new depth is higher than the previous one is dangerous. It will lead to a constantly increasing number of entries that will never be overwritten again, so the TT will become ineffective as the game progresses. Therefore using "depth preferred" as single replacement scheme is usually not successful. As a first step (before trying more advanced replacement schemes), checking of the depth can be omitted.

[theturk1234]

Hi Sven,
Yes, my TT is small because I recently implemented it and I haven't gotten around to making it bigger. It'll just take a second, so I'll get to it.
TT is the transposition table itself.
You can use a name in its own namespace without using the qualifier TT.whatever. I'm in TranspositionTable::probe(), so I don't have to use TT.table, just table. Do you understand?

Thanks,
David

[Sven]

Yes, my TT is small because I recently implemented it and I haven't gotten around to making it bigger. It'll just take a second, so I'll get to it.

Ok. Also most implementations use a table size which is a power of 2. Currently I'm not sure about the implications of not doing so.

TT is the transposition table itself.
You can use a name in its own namespace without using the qualifier TT.whatever. I'm in TranspositionTable::probe(), so I don't have to use TT.table, just table. Do you understand?

Not quite ... "TranspositionTable" is the class name, right? So what kind of name is "TT"? A namespace? If so, why would you need both a namespace and a class? And why do you use both "TT.whatever" and "whatever [without TT]" in the same context, why not consistently using only one style? If TT is a namespace and you want to keep it, fine, but as you said, you can omit it here, so why do you once omit it and once you don't?

[Aleks Peshkov]

TT is the transposition table itself.
You can use a name in its own namespace without using the qualifier TT.whatever. I'm in TranspositionTable::probe(), so I don't have to use TT.table, just table. Do you understand?

Do you know what is namespace, the C++ syntax of using namespaces? TT is the concrete instance of an object, it is not a namespace, nor a "qualifier" whatever.

Do you understand the difference between object method and static function?

[Sven]

TT is the transposition table itself.
You can use a name in its own namespace without using the qualifier TT.whatever. I'm in TranspositionTable::probe(), so I don't have to use TT.table, just table. Do you understand?

Do you know what is namespace, the C++ syntax of using namespaces? TT is the concrete instance of an object, it is not a namespace, nor a "qualifier" whatever.

Do you understand the difference between object method and static function?

Good remark, I missed that he wrote "TT." instead of "TT::" so TT can't be a namespace. So obviously TT is some instance of class TranspositionTable, which leaves my question open why once TT.table[index] is used and once only "table[index]". In general this is considered a bug.

[theturk1234]

Sven:
You're absolutely right! I should be at least consistent with the way I use TT. Yes, TT is an instance of the class TranspositionTable. I was just inconsistent, I'll have to fix it.
Sharp eye though, good job!
I haven't had too much time to look at the quality of the code, I'm mostly trying to get all the functionality in and then make the code "clean". I understand that this is not good programming practice and I have to work on it.

Thanks for the responses,
David Cimbalista