Multi-agent Solution for ‘8 Queens’ Puzzle

Ivan Babanin, Ivan Pustovoj, Elena Kleimenova, Sergey Kozhevnikov, Elena Simonova, Petr Skobelev, Alexander Tsarev

2012

Abstract

The problem of 8 Queens is one of the most well-known combinatorial problems. In this article multi-agent evolutionary-based solution for ‘8 Queens’ problem is proposed. In the multi-agent solution each Queen (or other chess-man) gets a software agent that uses a 'trial-and-error' method in asynchronous and parallel decision making on selecting new position for queens. As the result the solution is found in distributed manner without main control center that provides a number of benefits, for example, introducing new types of chess-man or changing constraints in real time. Two main strategies of Queen’s decision making process has been considered and compared in experiments: random generation of the next move and conflict-solving negotiations between the agents. Experiments’ results show significant acceleration of the decision making process in case of negotiation-based strategy. This solution was developed for training course for students of Computer Science as a methodical basis for designing swarm-based multi-agent systems for solving such complex problems as resource allocation and scheduling, pattern recognition or text understanding.

Paper Citation

in Harvard Style

Babanin I., Pustovoj I., Kleimenova E., Kozhevnikov S., Simonova E., Skobelev P. and Tsarev A. (2012). Multi-agent Solution for ‘8 Queens’ Puzzle . In Proceedings of the 4th International Joint Conference on Computational Intelligence - Volume 1: ECTA, (IJCCI 2012) ISBN 978-989-8565-33-4, pages 278-281. DOI: 10.5220/0004148502780281

in Bibtex Style

@conference{ecta12,
author={Ivan Babanin and Ivan Pustovoj and Elena Kleimenova and Sergey Kozhevnikov and Elena Simonova and Petr Skobelev and Alexander Tsarev},
title={Multi-agent Solution for ‘8 Queens’ Puzzle},
booktitle={Proceedings of the 4th International Joint Conference on Computational Intelligence - Volume 1: ECTA, (IJCCI 2012)},
year={2012},
pages={278-281},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0004148502780281},
isbn={978-989-8565-33-4},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 4th International Joint Conference on Computational Intelligence - Volume 1: ECTA, (IJCCI 2012)
TI - Multi-agent Solution for ‘8 Queens’ Puzzle
SN - 978-989-8565-33-4
AU - Babanin I.
AU - Pustovoj I.
AU - Kleimenova E.
AU - Kozhevnikov S.
AU - Simonova E.
AU - Skobelev P.
AU - Tsarev A.
PY - 2012
SP - 278
EP - 281
DO - 10.5220/0004148502780281