[논문]퍼펙트 9 다트 조합의 나눗셈 분기한정 알고리즘

이상운

doi:10.7236/jiibc.2022.22.4.87

초록
AI-Helper

본 논문은 501 다트게임의 최소 다트 촉 투척 횟수인 9회에 대한 획득점수 조합을 찾는 연구를 수행하였다. 다트게임에서 한 번 투척으로 획득할 수 있는 최대 점수는 60점으로 60×8+21×1=501에 의거 60점을 8회, 21점을 1회 획득하면 9회 투척으로 퍼펙트 다트게임을 종료할 수 있다. 이를 9-다트 종료라 한다. 이와 같이 9회 투척으로 501점을 획득 가능한 점수의 조합에 관한 연구는 18개와 14개만 알려져 있으며, 전수탐색 알고리즘을 적용한 연구는 수행되지 않고 있다. 본 논문은 전형적인 전수탐색법인 분기한정법의 O(2ⁿ) 지수시간 수행 복잡도를 다항시간 복잡도로 단순화 시키는 방법으로 나눗셈 분기한정 알고리즘을 제안하였다. 제안된 방법은 레벨을 8로 한정시키고, 501/60의 몫 레벨로 점프하고 역추적으로 이전 단계에서의 가능한 점수 조합만을 탐색하는 방법을 적용하였다. 제안된 알고리즘으로 찾은 9회의 퍼펙트게임의 가능한 점수 조합은 90개(101개 경우)를 얻었다.

Abstract ▼ AI-Helper

This paper researched a study to find a combination of acquisition scores for 9 dart throws, which is the minimum number of dart tactile throws in 501 point dart games. The maximum score that can be obtained by throwing once in a dart game is 60 points, which can end the perfect dart game with 60 po...

This paper researched a study to find a combination of acquisition scores for 9 dart throws, which is the minimum number of dart tactile throws in 501 point dart games. The maximum score that can be obtained by throwing once in a dart game is 60 points, which can end the perfect dart game with 60 points eight times according to 60×8+21×1=501, and if you earn 21 points once, you can finish the game with 9 throws. This is called 9-dart finish. As such, only 18 and 14 studies on the combination of scores that can obtain 501 points with 9 throws are known, and no studies have been conducted applying the exhaustive search algorithm. This paper proposed a division branch-and-bound algorithm as a method of simplifying the O(2n) exponential time performance complexity of the typical branch-and-bound method of a exhaustive search method, to polynomial time complexity. The proposed method limited the level to 8, jumped to a quotient level of 501/60, and backtracked to explore only possible score combinations in the previous level. The possible score combinations of the nine perfect games found with the proposed algorithm were 90(101 cases).

주제어

표/그림 (4)

그림 그림 1. 다트 게임과 점수 Fig. 1. Dart game & Scores
그림 그림 2. 501 9-다트 게임 종료 조합 Fig. 2. Combinations for 501 9-dart finish
그림 그림 3. s_i = 60, x_j = 7에 대한 DBBA Fig. 3. DBBA for s_i = 60, x_j = 7
표 표 1. C = 501, z = 9의 퍼펙트 다트게임 점수 경우 수 Table 1. Perfect dart game score cases for C = 501, z = 9

AI 본문요약
AI-Helper

문제 정의

본 논문에서는 9-다트 경기 종료 문제(9-dart finish problem, 9-DFP)의 501점을 9회 투척으로 획득할 수 있는 가능한 모든 경우 수인 조합을 찾는 알고리즘을 제안한다. 2장에서는 다트게임 방법과 9-DFP의 501점 획득 경우 수와 관련된 연구 결과를 고찰한다.
본 논문은 S=501점의 점수를 획득하여 퍼펙트 다트게임의 승자가 되기 위해 9회의 다트 촉을 던지는 경우 가능한 획득 점수의 조합 경우 수가 몇 개인지 정확히 찾아내는 알고리즘을 제안하였다.

제안 방법

이와 같이 최대 18가지 경우 수만 존재하는지 여부를 검증하기 위해 3장에서는 역 치환 알고리즘(RSA)을 제안하여 전수탐색(exhaustive search)하고자 한다.

이론/모형

본 장에서는 3장에서 제안된 나눗셈 분기한정 알고리즘(DBBA)을 적용하여 C=501의 z=9에 대한 가능한 경우 수를 표 1과 같이 찾을 수 있었다.

성능/효과

제안된 알고리즘을 501 9-다트 퍼펙트게임에 적용한 결과 기존에 알려진 18가지 경우 수에 비해 101가지 경우 수가 있음을 보였다.

참고문헌 (11)

Wikipedia, "Nine-Dart Finish," https://en.wikipedia.org/wiki/Nine-dart_finish, Retrieved Feb. 2022.
Wikipedia, "Darts," https://en.wikipedia.org/wiki/Darts#Scoring, Retrieved Feb. 2022.
Lardydarts, "Getting a Nine Dart Finish: How to Throw Like a Pro and Get a Nine Dart Finish," https://www.lardydarts.com/how-to/9-dart-finish, Retrieved Feb. 2022.
D. Boyle, "In Search of the Nine Dart Finish: Understanding Standards in a Time of Frustration," https://www.linkedin.com/pulse/search-nine-dart-finish-unrelenting-standards-time-david-boyle, Nov. 2020.
P. Lees, "Possible Mathematical Finishes to the Darts Game 501," https://www.titanwolf.org/Network/q/fbbfddde-6f93-4348-b443-ac3c664e598c/x, Retrieved Feb. 2022.
Jesscowie96, "The Math Behind the Perfect Nine-Dart Finish," https://shipmitreb.wordpress.com/2017/03/08/the-math-behind-the-perfect-nine-dart-finish/, Mar. 2017.
Northstandchat, "Thread: 9 Dart Finish Combinations," https://www.northstandchat.com/showthread.php?140891-9-dart-finish-combinations, Retrieved Feb. 2022.
Quora, "How do You Get a 9 Dart Finish?," https://www.quora.com/How-do-you-get-a-9-dart-finish, Retrieved Feb. 2022.
Idswater, "How Many Combinations does a 9 Darter Have?,"https://idswater.com/2020/02/22/how-many-combinations-does-a-9-darter-have/,Feb. 2020.
Dartworld, "Dart World Q and A: Helpful Information," https://www.dartworld.com/dart-world-questions-answers.html,Retrieved Feb. 2022.
Dartn, "Alle 71 verschiedenen Wege zum 9-Darter," https://www.dartn.de/Liste_aller_9-Darter_Moeglichkeiten, Retrieved Feb. 2022.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

퍼펙트 9 다트 조합의 나눗셈 분기한정 알고리즘
Branch-and-Bound Algorithm for Division of Perfect Nine Dart Combinations 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

표/그림 (4)

표/그림 (4)

AI 본문요약
AI-Helper

문제 정의

제안 방법

이론/모형

성능/효과

참고문헌 (11)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

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

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

선택된 텍스트

연합인증

퍼펙트 9 다트 조합의 나눗셈 분기한정 알고리즘 Branch-and-Bound Algorithm for Division of Perfect Nine Dart Combinations 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

표/그림 (4) 모든 표/그림 보기

표/그림 (4) 슬라이드로 보기

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

이론/모형

성능/효과

참고문헌 (11)

이 논문을 인용한 문헌

저자의 다른 논문 :

이상운 (199)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

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

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

선택된 텍스트

퍼펙트 9 다트 조합의 나눗셈 분기한정 알고리즘
Branch-and-Bound Algorithm for Division of Perfect Nine Dart Combinations 원문보기

초록
AI-Helper

표/그림 (4)

표/그림 (4)

AI 본문요약
AI-Helper