싱그럼의 연구실

https://ikki.app 이끼 - 온라인 끝말잇기이끼에서 사람들과 끝말잇기를 즐겨보세요. 구엜룰, 공밴룰, 천도룰, 끄투룰을 플레이할 수 있습니다.www.ikki.app 이끼는 온라인 1:1 끝말잇기 사이트입니다.- 현재는 구엜룰, 공밴룰, 천도룰, 끄투룰이 지원됩니다. (추후에 변동 가능)- 게임 시작 버튼을 누르면 랜덤으로 상대가 매칭됩니다.- 도전 링크를 생성하여 링크를 공유받은 사람과 플레이할 수도 있습니다.- 플레이 도중엔 자유롭게 검색할 수 있습니다. 그래서 루트 단어를 힘들게 외우지 않아도 되고, 키보드 없이 마우스, 터치만으로도 플레이할 수 있습니다. 모바일에서도요!- 모든 게임은 서버에 저장되어 누구나 쉽게 열람할 수 있습니다.- 레이팅을 기준으로 랭킹이 매겨집니다.  https:/..

제가 만든 끝말잇기 검색 사이트인 끄글( https://singrum.github.io/ggeugle/ )에서 필승 전략 탐색에 쓰고 있는 알고리즘은 깊이 우선 탐색(Depth First Search, DFS)의 변형인 탐욕적 최상 우선 탐색(Greedy Best First Search, GBFS)입니다. 어떤 포지션에서 상대방이 말할 수 있는 단어의 개수가 가장 작은 포지션을 먼저 탐색하는 방식의 깊이 우선 탐색이죠. 예를 들어 식에서는 식업, 식멸, 식읍, 식겁, 식균, 식식, 식민지리윤 순서로 탐색하게 됩니다. 끄글ㆍ끝말잇기 검색엔진 singrum.github.io 식업을 하면 상대방이 말할 수 있는 단어는 1개이고, 식멸은 2개, 식읍은 2개, 식겁은 4개, 식균은 6개, 식식은 7개, 식윤은 2..

이 블로그에 글을 안 올린지도 벌써 일 년 이상이 지났습니다. 대학생활 때문에 바쁘기도 했지만 2024년 1,2월에 끝말잇기 검색기 웹사이트인 끄글( singrum.github.io/ggeugle )을 업데이트하면서 끝말 관련 이론 연구를 꽤 많이 하게 되었습니다. 그 내용을 대략 정리해보면 1. 두음법칙을 고려하면 끝말잇기는 다중 유향 그래프가 아닌 '다중 하이퍼 유향 그래프'로 나타내어집니다. 따라서 다중 유향 그래프임을 가정하여 작성한 개념들을 조금 수정해야합니다. 2. 부분 이론으로 작성한 글에서 '부분'은 유향 그래프의 그래프 이론의 '약한 연결 요소'라는 개념과 일치합니다. 3. 순환 음절에서 루트 음절을 필터링하는 알고리즘을 개발했습니다. 입니다. 추후에 이 내용들에 대해서 포스팅하겠습니다.

https://singrum.github.io/ggeugle/ 끄글ㆍ끝말잇기 검색엔진 singrum.github.io  2022년 8월 19일에 제작을 결심하여 오늘 2022년 9월 11일에 깃허브 페이지를 통한 배포를 시작하였습니다.ui 이미지는 위와 같습니다.룰 설정 기능은 계속해서 추가해나갈 예정입니다.깃허브 링크https://github.com/singrum/ggeugle

설명 1. 끝말잇기를 구현한 이진 유향 그래프에서 간선의 방향을 모두 바꾼다. 각 음절에 내차수(음절로 들어가는 간선의 수)와 외차수(음절로부터 나오는 간선의 수), 카운터(음절의 외간선 중 승리 음절로부터 나온 간선의 수)를 할당한다. 처음 상태에서 승리 음절로 분류된 음절은 없으므로 모든 음절의 카운터는 0이다. 순환 음절 집합 \(C\)와 집합열 \(L_0, L_1, L_2, ...\)과 \(W_0, W_1, W_2, ...\)를 만든다. \(C\)에 모든 음절을 넣는다. 2. \(n := 0\) 3. \(C\)에서 '내차수 = 카운터'가 되는 음절을 \(L_n\)에 옮긴다. 만약 이러한 음절이 없다면 7로 이동 4. \(L_n\) 내의 모든 음절들에 대해 그 음절에서 나온 간선에 연결된 음절들을 ..

무향 끝말잇기 1. 선공은 무향 그래프 (좌측)에서 하나의 정점을 정하고 그 정점에 인접한 다른 정점을 선택하여 이동한다, 그리고 이동할 때 쓰인 간선은 지운다. 2. 후공은 선공이 선택한 정점에 인접한 다른 정점을 선택하여 이동한다. 그리고 이동할 때 쓰인 간선을 지운다. 3. 이 과정을 반복하여 더 이상 이동할 수 있는 정점이 없는 경우 패배한다. 예시 선공 : 4 -> 3 후공 : 3 -> 1 선공 : 1 -> 4 후공 : 4 -> 5 선공 : 5 -> 6 후공 : 6 -> 5 선공 : 5 -> 3 후공 패 유향 끝말잇기 1. 선공은 유향 그래프(우측)에서 하나의 정점을 정하고 그 정점에 화살표로 이어지는 다른 정점을 선택하여 이동한다. 그리고 이동할 때 쓰인 간선을 지운다. 2. 후공은 선공이 선..