Data structures for PN-search

Any topic that does not fit elsewhere
Post Reply
ingwa
Posts: 9
Joined: Sat Jan 02, 2016 3:17 am

Data structures for PN-search

Post by ingwa » Sat Jan 02, 2016 12:57 pm

I will test this new forum with a real question. :)

I have read a lot about PN-search and all its variations and improvements. One thing that I never saw anybody mention was how to represent the tree efficiently.

The naïve solution is to have a node with a vector or linked list of pointers to its children. But this is hardly the most efficient solution. What are the best data structure for representing a search tree for PN-search? Are there enhancements that are needed for enhancements like PN² or DF-PN? I am about to (re-)implement PN-search and I would want to take the right approach from the very beginning.

Rémi Coulom
Posts: 113
Joined: Tue Feb 12, 2008 8:31 pm
Contact:

Re: Data structures for PN-search

Post by Rémi Coulom » Sat Jan 02, 2016 1:37 pm

Hi,

Welcome, and thanks for participating in the forum.

I have no experience with implementing PN search, so I cannot give expert advice. But you'll probably find the answer to your question in section 5 of that paper, written by the experts:
https://webdocs.cs.ualberta.ca/~mmuelle ... 012PNS.pdf

Rémi

ingwa
Posts: 9
Joined: Sat Jan 02, 2016 3:17 am

Re: Data structures for PN-search

Post by ingwa » Sat Jan 02, 2016 4:09 pm

Rémi Coulom wrote:Hi,

Welcome, and thanks for participating in the forum.

I have no experience with implementing PN search, so I cannot give expert advice. But you'll probably find the answer to your question in section 5 of that paper, written by the experts:
https://webdocs.cs.ualberta.ca/~mmuelle ... 012PNS.pdf
Rémi
Hi Rémi and thanks for reopening it.

I have read that article before and liked it, since it's the best overview of PN search that I ever read. Section 5 talks about transposition tables which I didn't read very carefully since I regarded it only as a way to make the search quicker, not the way to represent the whole tree. But on closer inspection I see that they also hint of ways to use the TT as the actual storage of the tree. However, many of the details are hidden in the references so I hope that I will be able to get those online.

Thanks for the pointer!

-Inge

ingwa
Posts: 9
Joined: Sat Jan 02, 2016 3:17 am

Re: Data structures for PN-search

Post by ingwa » Sat Jan 02, 2016 8:39 pm

ingwa wrote: However, many of the details are hidden in the references so I hope that I will be able to get those online.
On this note, does anybody have the PDF for "Gnodde: New Search Techniques Applied to Othello"? It contains some interesting information and I have so far only seen it in lists, not the contents itself.

ingwa
Posts: 9
Joined: Sat Jan 02, 2016 3:17 am

Re: Data structures for PN-search

Post by ingwa » Fri Jan 08, 2016 1:56 pm

Nobody? Are there any people from the University of Leiden here?

Post Reply