Solving 7x7 Killall-Go with Seki Database Article Swipe

PDF

Yi Tyan Tsai , Wei Ting , C. Y. Lin , Chung‐Yang Shih , Hung Guei , I‐Chen Wu , Tongda Wu ·

YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2411.05565

Game solving is the process of finding the theoretical outcome for a game, assuming that all player choices are optimal. This paper focuses on a technique that can reduce the heuristic search space significantly for 7x7 Killall-Go. In Go and Killall-Go, live patterns are stones that are protected from opponent capture. Mutual life, also referred to as seki, is when both players' stones achieve life by sharing liberties with their opponent. Whichever player attempts to capture the opponent first will leave their own stones vulnerable. Therefore, it is critical to recognize seki patterns to avoid putting oneself in jeopardy. Recognizing seki can reduce the search depth significantly. In this paper, we enumerate all seki patterns up to a predetermined area size, then store these patterns into a seki table. This allows us to recognize seki during search, which significantly improves solving efficiency for the game of Killall-Go. Experiments show that a day-long, unsolvable position can be solved in 482 seconds with the addition of a seki table. For general positions, a 10% to 20% improvement in wall clock time and node count is observed.

Related Topics

Computer Science

Database

Concepts

Computer science Database

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2411.05565
PDF: https://arxiv.org/pdf/2411.05565
OA Status: green
Related Works: 10
OpenAlex ID: https://openalex.org/W4404389823

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4404389823

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2411.05565

Digital Object Identifier
Title: Solving 7x7 Killall-Go with Seki Database

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2024

Year of publication
Publication date: 2024-11-08

Full publication date if available
Authors: Yi Tyan Tsai, Wei Ting, C. Y. Lin, Chung‐Yang Shih, Hung Guei, I‐Chen Wu, Tongda Wu

List of authors in order
Landing page: https://arxiv.org/abs/2411.05565

Publisher landing page
PDF URL: https://arxiv.org/pdf/2411.05565

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2411.05565

Direct OA link when available
Concepts: Computer science, Database

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4404389823
doi	https://doi.org/10.48550/arxiv.2411.05565
ids.doi	https://doi.org/10.48550/arxiv.2411.05565
ids.openalex	https://openalex.org/W4404389823
fwci
type	preprint
title	Solving 7x7 Killall-Go with Seki Database
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T11574
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9042999744415283
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1702
topics[0].subfield.display_name	Artificial Intelligence
topics[0].display_name	Artificial Intelligence in Games
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C41008148
concepts[0].level	0
concepts[0].score	0.45781296491622925
concepts[0].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[0].display_name	Computer science
concepts[1].id	https://openalex.org/C77088390
concepts[1].level	1
concepts[1].score	0.42068326473236084
concepts[1].wikidata	https://www.wikidata.org/wiki/Q8513
concepts[1].display_name	Database
keywords[0].id	https://openalex.org/keywords/computer-science
keywords[0].score	0.45781296491622925
keywords[0].display_name	Computer science
keywords[1].id	https://openalex.org/keywords/database
keywords[1].score	0.42068326473236084
keywords[1].display_name	Database
language	en
locations[0].id	pmh:oai:arXiv.org:2411.05565
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2411.05565
locations[0].version	submittedVersion
locations[0].raw_type
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2411.05565
locations[1].id	doi:10.48550/arxiv.2411.05565
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2411.05565
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5003081319
authorships[0].author.orcid	https://orcid.org/0009-0007-6703-1687
authorships[0].author.display_name	Yi Tyan Tsai
authorships[0].author_position	first
authorships[0].raw_author_name	Tsai, Yun-Jui
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5120314168
authorships[1].author.orcid	https://orcid.org/0000-0001-9008-0339
authorships[1].author.display_name	Wei Ting
authorships[1].author_position	middle
authorships[1].raw_author_name	Wei, Ting Han
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5107895194
authorships[2].author.orcid
authorships[2].author.display_name	C. Y. Lin
authorships[2].author_position	middle
authorships[2].raw_author_name	Lin, Chi-Huang
authorships[2].is_corresponding	False
authorships[3].author.id	https://openalex.org/A5113498220
authorships[3].author.orcid
authorships[3].author.display_name	Chung‐Yang Shih
authorships[3].author_position	middle
authorships[3].raw_author_name	Shih, Chung-Chin
authorships[3].is_corresponding	False
authorships[4].author.id	https://openalex.org/A5114653602
authorships[4].author.orcid
authorships[4].author.display_name	Hung Guei
authorships[4].author_position	middle
authorships[4].raw_author_name	Guei, Hung
authorships[4].is_corresponding	False
authorships[5].author.id	https://openalex.org/A5016730899
authorships[5].author.orcid	https://orcid.org/0000-0003-2535-0587
authorships[5].author.display_name	I‐Chen Wu
authorships[5].author_position	middle
authorships[5].raw_author_name	Wu, I-Chen
authorships[5].is_corresponding	False
authorships[6].author.id	https://openalex.org/A5070455837
authorships[6].author.orcid	https://orcid.org/0000-0003-1339-884X
authorships[6].author.display_name	Tongda Wu
authorships[6].author_position	last
authorships[6].raw_author_name	Wu, Ti-Rong
authorships[6].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2411.05565
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Solving 7x7 Killall-Go with Seki Database
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T11574
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9042999744415283
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1702
primary_topic.subfield.display_name	Artificial Intelligence
primary_topic.display_name	Artificial Intelligence in Games
related_works	https://openalex.org/W4391375266, https://openalex.org/W2899084033, https://openalex.org/W2748952813, https://openalex.org/W2390279801, https://openalex.org/W4391913857, https://openalex.org/W2358668433, https://openalex.org/W4396701345, https://openalex.org/W2376932109, https://openalex.org/W2001405890, https://openalex.org/W4396696052
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2411.05565
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2411.05565
best_oa_location.version	submittedVersion
best_oa_location.raw_type
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2411.05565
primary_location.id	pmh:oai:arXiv.org:2411.05565
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2411.05565
primary_location.version	submittedVersion
primary_location.raw_type
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2411.05565
publication_date	2024-11-08
publication_year	2024
referenced_works_count	0
abstract_inverted_index.a	11, 24, 117, 126, 150, 164, 170
abstract_inverted_index.Go	38
abstract_inverted_index.In	37, 107
abstract_inverted_index.as	56
abstract_inverted_index.be	155
abstract_inverted_index.by	65
abstract_inverted_index.in	97, 157, 175
abstract_inverted_index.is	2, 58, 87, 182
abstract_inverted_index.it	86
abstract_inverted_index.of	5, 145, 163
abstract_inverted_index.on	23
abstract_inverted_index.to	55, 74, 89, 93, 116, 132, 172
abstract_inverted_index.up	115
abstract_inverted_index.us	131
abstract_inverted_index.we	110
abstract_inverted_index.10%	171
abstract_inverted_index.20%	173
abstract_inverted_index.482	158
abstract_inverted_index.7x7	35
abstract_inverted_index.For	167
abstract_inverted_index.all	15, 112
abstract_inverted_index.and	39, 179
abstract_inverted_index.are	18, 43, 46
abstract_inverted_index.can	27, 101, 154
abstract_inverted_index.for	10, 34, 142
abstract_inverted_index.own	82
abstract_inverted_index.the	3, 7, 29, 76, 103, 143, 161
abstract_inverted_index.Game	0
abstract_inverted_index.This	20, 129
abstract_inverted_index.also	53
abstract_inverted_index.area	119
abstract_inverted_index.both	60
abstract_inverted_index.from	48
abstract_inverted_index.game	144
abstract_inverted_index.into	125
abstract_inverted_index.life	64
abstract_inverted_index.live	41
abstract_inverted_index.node	180
abstract_inverted_index.seki	91, 100, 113, 127, 134, 165
abstract_inverted_index.show	148
abstract_inverted_index.that	14, 26, 45, 149
abstract_inverted_index.then	121
abstract_inverted_index.this	108
abstract_inverted_index.time	178
abstract_inverted_index.wall	176
abstract_inverted_index.when	59
abstract_inverted_index.will	79
abstract_inverted_index.with	68, 160
abstract_inverted_index.avoid	94
abstract_inverted_index.clock	177
abstract_inverted_index.count	181
abstract_inverted_index.depth	105
abstract_inverted_index.first	78
abstract_inverted_index.game,	12
abstract_inverted_index.leave	80
abstract_inverted_index.life,	52
abstract_inverted_index.paper	21
abstract_inverted_index.seki,	57
abstract_inverted_index.size,	120
abstract_inverted_index.space	32
abstract_inverted_index.store	122
abstract_inverted_index.their	69, 81
abstract_inverted_index.these	123
abstract_inverted_index.which	137
abstract_inverted_index.Mutual	51
abstract_inverted_index.allows	130
abstract_inverted_index.during	135
abstract_inverted_index.paper,	109
abstract_inverted_index.player	16, 72
abstract_inverted_index.reduce	28, 102
abstract_inverted_index.search	31, 104
abstract_inverted_index.solved	156
abstract_inverted_index.stones	44, 62, 83
abstract_inverted_index.table.	128, 166
abstract_inverted_index.achieve	63
abstract_inverted_index.capture	75
abstract_inverted_index.choices	17
abstract_inverted_index.finding	6
abstract_inverted_index.focuses	22
abstract_inverted_index.general	168
abstract_inverted_index.oneself	96
abstract_inverted_index.outcome	9
abstract_inverted_index.process	4
abstract_inverted_index.putting	95
abstract_inverted_index.search,	136
abstract_inverted_index.seconds	159
abstract_inverted_index.sharing	66
abstract_inverted_index.solving	1, 140
abstract_inverted_index.addition	162
abstract_inverted_index.assuming	13
abstract_inverted_index.attempts	73
abstract_inverted_index.capture.	50
abstract_inverted_index.critical	88
abstract_inverted_index.improves	139
abstract_inverted_index.opponent	49, 77
abstract_inverted_index.optimal.	19
abstract_inverted_index.patterns	42, 92, 114, 124
abstract_inverted_index.players'	61
abstract_inverted_index.position	153
abstract_inverted_index.referred	54
abstract_inverted_index.Whichever	71
abstract_inverted_index.day-long,	151
abstract_inverted_index.enumerate	111
abstract_inverted_index.heuristic	30
abstract_inverted_index.jeopardy.	98
abstract_inverted_index.liberties	67
abstract_inverted_index.observed.	183
abstract_inverted_index.opponent.	70
abstract_inverted_index.protected	47
abstract_inverted_index.recognize	90, 133
abstract_inverted_index.technique	25
abstract_inverted_index.Therefore,	85
abstract_inverted_index.efficiency	141
abstract_inverted_index.positions,	169
abstract_inverted_index.unsolvable	152
abstract_inverted_index.Experiments	147
abstract_inverted_index.Killall-Go,	40
abstract_inverted_index.Killall-Go.	36, 146
abstract_inverted_index.Recognizing	99
abstract_inverted_index.improvement	174
abstract_inverted_index.theoretical	8
abstract_inverted_index.vulnerable.	84
abstract_inverted_index.predetermined	118
abstract_inverted_index.significantly	33, 138
abstract_inverted_index.significantly.	106
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	7
citation_normalized_percentile