Efficient Search Using Bitboard Models

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Pablo San Segundo Articles by Ramon Galan Articles by Fernando Matia Articles by Diego Rodriguez-Losada Articles by Agustin Jimenez

18th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'06)

Arlington, Virginia

November 13-November 15

ISBN: 0-7695-2728-0

	ASCII Text	x
	Pablo San Segundo, Ramon Galan, Fernando Matia, Diego Rodriguez-Losada, Agustin Jimenez, "Efficient Search Using Bitboard Models," Tools with Artificial Intelligence, IEEE International Conference on, pp. 132-138, 18th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'06), 2006.

	BibTex	x
	@article{ 10.1109/ICTAI.2006.53, author = {Pablo San Segundo and Ramon Galan and Fernando Matia and Diego Rodriguez-Losada and Agustin Jimenez}, title = {Efficient Search Using Bitboard Models}, journal ={Tools with Artificial Intelligence, IEEE International Conference on}, volume = {0}, year = {2006}, issn = {1082-3409}, pages = {132-138}, doi = {http://doi.ieeecomputersociety.org/10.1109/ICTAI.2006.53}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Tools with Artificial Intelligence, IEEE International Conference on TI - Efficient Search Using Bitboard Models SN - 1082-3409 SP132 EP138 A1 - Pablo San Segundo, A1 - Ramon Galan, A1 - Fernando Matia, A1 - Diego Rodriguez-Losada, A1 - Agustin Jimenez, PY - 2006 KW - null VL - 0 JA - Tools with Artificial Intelligence, IEEE International Conference on ER -

Pablo San Segundo, Universidad Politecnica de Madrid, Spain

Ramon Galan, Universidad Politecnica de Madrid, Spain

Fernando Matia, Universidad Politecnica de Madrid, Spain

Diego Rodriguez-Losada, Universidad Politecnica de Madrid, Spain

Agustin Jimenez, Universidad Politecnica de Madrid, Spain

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICTAI.2006.53

This paper shows a way to speed up search by using an encoding at bit level to model a particular domain. A bitboard is an unsigned integer whose bits have been given an interpretation in the world of discourse. In models encoded in such a way, states will be described internally as a set of bitboard tuples, whilst operators which allow for transitions between states are essentially bitwise operations over elements belonging to that set.

Given a 64-bit processor word, for each transition it would be theoretically possible to reach another state 64 times faster than with a normal encoding, fast transitions being one of the main issues for efficient search algorithms. We have analysed some other key issues related to efficient bitboard model design and formalised the concepts of well formed heuristics and bitboard guides.

We have used this approach to solve instances of the maximum clique problem thus increasing the performance of one of the fastest algorithms known in the domain for optimal search.

Citation:

Pablo San Segundo, Ramon Galan, Fernando Matia, Diego Rodriguez-Losada, Agustin Jimenez, "Efficient Search Using Bitboard Models," ictai, pp.132-138, 18th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'06), 2006

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.