$\require{mediawiki-texvc}$

연합인증

연합인증 가입 기관의 연구자들은 소속기관의 인증정보(ID와 암호)를 이용해 다른 대학, 연구기관, 서비스 공급자의 다양한 온라인 자원과 연구 데이터를 이용할 수 있습니다.

이는 여행자가 자국에서 발행 받은 여권으로 세계 각국을 자유롭게 여행할 수 있는 것과 같습니다.

연합인증으로 이용이 가능한 서비스는 NTIS, DataON, Edison, Kafe, Webinar 등이 있습니다.

한번의 인증절차만으로 연합인증 가입 서비스에 추가 로그인 없이 이용이 가능합니다.

다만, 연합인증을 위해서는 최초 1회만 인증 절차가 필요합니다. (회원이 아닐 경우 회원 가입이 필요합니다.)

연합인증 절차는 다음과 같습니다.

최초이용시에는
ScienceON에 로그인 → 연합인증 서비스 접속 → 로그인 (본인 확인 또는 회원가입) → 서비스 이용

그 이후에는
ScienceON 로그인 → 연합인증 서비스 접속 → 서비스 이용

연합인증을 활용하시면 KISTI가 제공하는 다양한 서비스를 편리하게 이용하실 수 있습니다.

무전략 몬테카를로 트리탐색을 활용한 9줄바둑에서의 첫 수
The first move in the game of 9⨯9 Go, using non-strategic Monte-Carlo Tree Search 원문보기

한국게임학회 논문지 = Journal of Korea Game Society, v.17 no.3, 2017년, pp.63 - 70  

이병두 (세한대학교 체육학부 바둑학과)

초록
AI-Helper 아이콘AI-Helper

인공지능 연구에서 바둑은 위치평가의 어려움과 엄청난 분기수로 인해 가장 도전적인 보드게임으로 여겨지고 있다. 몬테카를로 트리탐색은 이러한 문제점을 극복할 수 있는 고무적인 돌파구이다. 알파고의 숨겨진 아이디어는 주어진 위치에서의 승률을 예상하여 깊은 탐색을 유도한 후 가장 고무적인 착수를 찾아내는 것이었다. 본 논문에서는 무전략 MCTS를 활용하여 9줄바둑에서 프로기사들이 최상의 첫수로 여기는 천원점이 옳다는 것을 확인했으며, 또한 가장 유행하는 첫 수들의 평균승률을 비교했다.

Abstract ▼ AI-Helper 아이콘AI-Helper

In AI research Go is regarded as the most challenging board game due to the positional evaluation difficulty and the huge branching factor. MCTS is an exciting breakthrough to overcome these problems. The idea behind AlphaGo was to estimate the winning rate of a given position and then to lead deepe...

주제어

#9줄바둑   #위치평가   #분기수   #몬테카를로 트리탐색   #첫수   #천원점  

AI 본문요약
AI-Helper 아이콘 AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

  • 본 논문에서는 아무런 전략이 없는 순수 MCTS를 활용하여 19줄바둑의 축소판인 9줄바둑에서 덤(공제: komi)을 고려한 최상의 첫 수를 구하고자 했다.
  • 저자는 AlphaGo 알고리즘의 근간이 되는 MCTS를 활용하여 9줄바둑에서의 최상의 첫 수를 구하고자 했다. 실험결과에 따르면 (1)프로기사들이 막연히 최상의 첫수가 천원점이라고 여기는 것이 통계학적으로 옳다는 사실(4.
본문요약 정보가 도움이 되었나요?

질의응답

핵심어 질문 논문에서 추출한 답변
바둑은 어떤 단계로 진행되는가? 바둑은 두 대국자가 흑과 백의 바둑돌로 규칙을 준수하며, 19줄(19⨯19) 바둑판 위 361개의 교차점에 교대로 착수하여 쌍방이 차지한 집과 사석(잡은 돌)의 많고 적음으로 승패를 가리는 경기이다[10]. 한 판의 바둑은 초반, 중반, 종반으로 구분하고 있으며, 초반은 영토의 기본 골격을 구축하는 포석 단계, 중반은 전투 행위를 하는 단계, 종반은 영토의 경계를 마무리하는 끝내기 단계가 된다.
바둑에서 귀에 두는 수로는 무엇이 있는가? 포석 단계에서의 첫 수는 영토를 차지하기 유리한 곳인, 즉 모서리 부근의 두 지역이 막혀있는 귀에 둔다. 귀에 두는 수로는 화점(Star point or Hoshi), 소목(Small eye or Komok), 3삼(Three by three or Sansan), 외목(Outside the eye or Mokuhazushi), 고목(High eye or Takamoku)의 다섯 가지가 사용되며[12], 현대 바둑에서는 화점과 소목을 압도적으로 많이 두고 있다[13].
MCTS(몬테카를로 트리탐색)는 어떤 단계를 거치며 진행되는가? ☐ 선택(selection): 트리정책(tree policy)을 적용하여 단말노드를 만날 때까지 계속하여 확장 안된 노드를 선택해 나간다. ☐ 확장(expansion): 선택단계에서 정해진 자식 노드가 탐색트리에 첨가된다. ☐ 시뮬레이션(simulation): 디폴트정책(default policy)에 의거 단말노드를 만날 때까지 몬테카를로 시뮬레이션을 지속한다.  ☐ 역전파(backpropagation): 시뮬레이션에서 구해진 보상값을 뿌리노드로 역전파하며 통계량을 갱신한다.
질의응답 정보가 도움이 되었나요?

참고문헌 (24)

  1. B.D. Lee, "Enhanced strategic Monte-Carlo Tree Search algorithm to play the game of Tic-Tac-Toe", Journal of Korea Game Society, Vol. 16, No. 4, pp. 79-86, 2016. 

  2. B.D. Lee, D.S. Park and Y.W. Choi, "The UCT algorithm applied to find the best first move in the game of Tic-Tac-Toe", Journal of Korea Game Society, Vol. 15, No. 5, pp. 109-118, 2015. 

    원문보기 상세보기 crossref

  3. B.D. Lee, "Competition between MCTS and UCT in the game of Tic-Tac-Toe", Journal of Korean Society for Computer Game, Vol. 29, No. 1, pp. 1-6, 2016. 

    상세보기 crossref

  4. B.D. Lee, "Analysis of Tic-Tac-Toe Game Strategies using Genetic Algorithm", Journal of Korea Game Society, Vol. 14, No. 6, pp. 39-48, 2014. 

  5. B.D. Lee, "Monte-Carlo Tree Search Applied to the Game of Tic-Tac-Toe", Journal of Korea Game Society, Vol. 14, No. 3, pp. 47-54, 2014. 

    원문보기 상세보기 crossref

  6. B.D. Lee and Y.W. Choi, "Monte-Carlo Game Implementation", Hansan Press, 2017. 

  7. A. Couetoux, M. Muller and O. Teytaud, "Monte Carlo Tree Search in Go", from https://webdocs.cs.ualberta.ca/-mmueller/ps/2013/2013-gochapter-preprint.pdf, 2017. 

  8. D. Silver, et al., "Mastering the game of Go with deep neural networks and tree search", Journal of Nature, Vol. 529, Issue 7587, pp. 484-489, 2016. 

    상세보기 crossref

  9. T. Song, "Monte Carlo Tree Search and Its Application in AlphaGo", from https://stlong0521.github.io/20160409%20-%20MCTS.html, 2017. 

  10. S.H. Jung, et al., "Modern Baduk theory", Dacom Press, 2016. 

  11. Wikipedia, "Komidashi", from https://en.wikipedia.org/wiki/Komidashi, 2017. 

  12. Wikipedia, "List of Go terms", from https://en.wikipedia.org/wiki/List_of_Go_terms 

  13. Sensei's Library, " $9{\times}9$ Openings", from http://senseis.xmp.net/?9x9Openings, 2017. 

  14. H. Baier and M.H.M. Winands, "Monte-carlo Tree Search and Minimax Hybrids", Computer Games, Vol. 504, pp. 45-63, 2014. 

  15. M.H.M. Winands and Y. Brornsson, "Evaluation Function Based Monte-Carlo LOA", from http://www.ru.is/-yngvi/pdf/WinandsB09.pdf, 2017. 

  16. A.A.J van der Kleij, "Monte Carlo Tree Search and Opponent Modeling through Player Clustering in no-limit Texas Hold'en Poker", Master thesis, University of Groningen, 2010. 

  17. E. Powley, et al, "Heuristic move pruning in monte carlo tree search for the strategic card game lords of war", In Computational Intelligence and Games (CIG) of IEEE, pp.1-7, 2014. 

  18. B.D. Lee, "Evolutionary neural network model for recognizing strategic fitness of a finished Tic-Tac-Toe game", Journal of Korean Society for Computer Game, Vol. 28, No. 2, pp. 95-101, 2015. 

  19. B.D. Lee, "Implementation of robust Tic-Tac-Toe game player, using enhanced Monte-Carlo algorithm", Journal of Korean Society for Computer Game, Vol. 26, No. 3, pp. 135-141, 2015. 

  20. B.D. Lee and Y.W. Choi, "The best move sequence in playing Tic-Tac-Toe game", Journal of The Korean Society for Computer Game, Vol. 27, No. 3, pp. 11-16, 2014. 

  21. B.D. Lee, "Comparison of LDA and PCA for Korean Pro Go Player's Opening Recognition", Journal of Korea Game Society, Vol. 13, No. 4, pp. 15-24, 2013. 

  22. B.D. Lee, "Analysis of Korean, Chinese and Japanese Pro Go Player's Openings", Journal of Korean Society for Computer Game, Vol. 26, No. 4, pp. 17-26, 2013. 

  23. B.D. Lee, "Korean Pro Go Player's Opening Recognition Using PCA", Journal of Korean Society for Computer Game, Vol. 26, No. 2, pp. 228-233, 2013. 

  24. S. Gelly, et al., "The Grand Challenge of Computer Go: Monte Carlo Tree Search and Extensions", Communications of the ACM, Vol. 55, No. 3, pp. 106-113, 2012. 

    상세보기

저자의 다른 논문 :

관련 콘텐츠

오픈액세스(OA) 유형

FREE

Free Access. 출판사/학술단체 등이 허락한 무료 공개 사이트를 통해 자유로운 이용이 가능한 논문

이 논문과 함께 이용한 콘텐츠

섹션별 컨텐츠 바로가기

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

AI-Helper 아이콘
AI-Helper
안녕하세요, AI-Helper입니다. 좌측 "선택된 텍스트"에서 텍스트를 선택하여 요약, 번역, 용어설명을 실행하세요.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.

선택된 텍스트

맨위로