Zastosowanie komputerów w dziedzinie wyszukiwania strategii optymalnych w grach logicznych

• Autorzy: Goluch T.

Warianty tytułu

EN

Computer use in finding the optimal strategy in logic games

• Konferencja: GDAŃSKIE DNI ELEKTRYKI (XXXVII ; 11-12.10.2012 ; Gdańsk, Polska)
• Języki publikacji: PL

Abstrakty

PL

Problem jaki stanowi wyszukiwanie strategii optymalnej w grach logicznych jest bardzo złożony. Można go podzielić na następujące podproblemy: obliczeniowy, pamięciowy oraz operacji wejścia/wyjścia. Jednak rosnąca z roku na rok siła obliczeniowa komputerów, ilość pamięci oraz prędkość transferu danych pomiędzy podzespołami zarówno lokalnymi jak i rozproszonymi, a także wzrost skuteczności wykorzystywanych technik algorytmicznych powoduje, że komputery zaczynają grać doskonale, realizując strategie optymalne. W pierwszej części tej pracy przedstawiono początkowe próby skonstruowania inteligentnego sztucznego gracza. W kolejnym punkcie przedstawiono w układzie chronologicznym większość nietrywialnych, rozwiązanych gier. Trzeci punkt dotyczy aktualnego stanu wiedzy oraz perspektyw co do możliwości rozwiązania najbardziej popularnych gier.

EN

The issue of search an optimal strategy in logic games is a complex one. It can be divided into three sub-issues: computational, mnemonic and input/output operational. However, the ever-expanding computational and mnemonic powers of computers, as well as the speed in which local and distributed subdomains can transfer data, and the increased effectiveness help computers play better and better. In the first part of the thesis the early attempts of creating a AI player have been presented. In the following chapter non-trivial game solutions have been presented in chronological order. The third chapter describes the current knowledge and perspectives for solving the most popular games.

Słowa kluczowe

PL

rozwiązywanie gier; sztuczna inteligencja; gra logiczna

EN

solving games; artificial intelligence; logic game

• Wydawca: Wydział Elektrotechniki i Automatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału Elektrotechniki i Automatyki Politechniki Gdańskiej
• Rocznik: 2012
• Tom: Nr 31
• Strony: 57--60
• Opis fizyczny: Bibliogr. 25 poz., tab.

Twórcy

autor

Goluch T.

• Politechnika Gdańska, Wydział Elektroniki Telekomunikacji i Informatyki, Katedra Algorytmów i Modelowania Systemów tel: [phone],

Bibliografia

• 1. Shannon C. E., Programming a computer for playing chess. Philosophical Magazine, 7th series, 41(314) s. 256-75, 1950.
• 2. Patashnik O., Qubic: 4x4x4 tic-tac-toe, Mathematics Magazine, (53) s. 202-216, 1980.
• 3. Allen J., A note on the computer solution of Connect-Four, D.N.L. Levy, D.F. Beal (Eds.), Heuristic Programming in Artifcial Intelligence: the First Computer Olympiad, Ellis Horwood, Chichester, s. 134-135, 1989.
• 4. Allis L. V., Herik, H.J. van den, Huntjens M. P. H., Go-Moku and Threat-Space Search, Rap. tech. CS 93-02, Department of Computer Science, Faculty of General Sciences, Rijksuniversiteit Limburg, Maastricht, Netherlands 1993.
• 5. Gasser R., Solving Nine Men’s Morris, Games of No Chance (ed. R. Nowakowski) , MSRI Publications (29), s. 101-113. Cambridge University Press, Cambridge, 1996.
• 6. Orman H. K., The Game of Pentominoes: A First Player Win, Games of No Chance, 29, s. 339-344, Cambridge University Press, 1994.
• 7. Holshouser A., Reiter H., Mathematics and Informatics Quarterly, Quarto without the Twist, 16(2) s. 50-55, 2005.
• 8. Weisstein, E. W., "Teeko." MathWorld-A Wolfram Web Resource. URL http://mathworld.wolfram.com/Teeko.html.
• 9. Donkers, H. H. L. M., Voogt, A. J. de, Uiterwijk, J. W. H. M. Human versus Machine Problem-Solving: Winning Openings in Dakon, Board Games Studies; 3: 79-88, 2000.
• 10. Herik, H.J. van den, Uiterwijk, J.W.H.M., Rijswick, J. van. Games Solved: Now and in the Future. Artificial Intelligence, Vol. 134, Nos. 1-2, s. 277-311, 2002, ISSN 0304-3975.
• 11. Breuker D., Uiterwijk J., Herik J. van den. Solving 8 × 8 Domineering. Theoretical Computer Science, (230), p. 195-206, 2000, ISSN 0304-3975.
• 12. Irving, G., Donkers, H. H. L. M., Uiterwijk, J. W. H. M., Solving Kalah. ICGA Journal, Vol. 23, (3), s. 139–148, 2000.
• 13. Wagner, J., Virag, I.: Solving Renju, ICGA Journal, 24 (1), 30–34, 2001.
• 14. Romein, J.W. and Bal, H.E., Awari is Solved. ICGA Journal, 25(3), s. 162-165, 2002.
• 15. Yew J. L., On Forward Pruning in Game-Tree Search. Praca magisterska, National University of Singapore, 2007.
• 16. Schaeffer J., Checkers Is Solved, Science, 317(5844) s. 1518–1522 2007.
• 17. Schadd M. P. D., Winands M. H. M., Uiterwijk J. W. H. M., Herik H. J. van den, Bergsma M. H. J., Best Play In Fanorona Leads To Draw, New Mathematics and Natural Computation, 4(03) s. 369-387, 2008.
• 18. Jin L. Y., Nievergelt J., Computing Tigers and Goats, ICGA Journal, 27(3), s. 131-141. ISSN 1389-6911, 2004.
• 19. Sackson S., A Gamut of Games, Hutchinson, London, 1982.
• 20. Sakuta M., Iida H., The Performance Of Pn*, Pds, And Pn Search On 6x6 Othello And Tsume-Shogi, Advances in Computer Games, 9 s. 203–222 2001.
• 21. Grimminick M. URL http://www.xs4all.nl/~mdgsoft/draughts/stats/index.html.
• 22. Arneson B., Hayward, R.B., Henderson, P., Solving Hex: Beyond Humans. Computers and Games, s. 1-10, 2010.
• 23. Kryukov K., 4x4 Chess, URL http://kirill-kryukov.com/chess/4x4-chess/about.html
• 24. Werf E. van der, Herik J. van den, Uiterwijk J., Solving Go on small boards. ICGA Journal, 26(2) s.92–107, 2003.
• 25. Werf E. van der, Winands M. H. M., Solving Go for Rectangular Boards. Journal of The International