Minesweeper

Сапер (англ. Minesweeper) — жанр логічної головоломки, в яку зазвичай грають на персональних комп'ютерах. У грі є сітка клікабельних квадратів із прихованими «мінами», розкиданими по дошці. Мета полягає в тому, щоб очистити дошку, не підірвавши жодної міни, використовуючи підказки щодо кількості мін поруч із кожним квадратом. Створено варіанти гри, які розширюють основні концепції, такі як Minesweeper X, Crossmines і Minehunt. «Сапер» включено як ^[en] в інші ігри, такі як RuneScape і першоквітневе оновлення Minecraft 2015 року.

Виграна експертна гра ^[en], безкоштовного варіанту Minesweeper з відкритим кодом

Походження «Сапера» неясне. За даними TechRadar, першою версією гри був ^[en] 1990-х років, але Eurogamer каже, що першою була гра ^{[en] [en]} (1983). Курт Джонсон, творець Microsoft Minesweeper, визнає, що дизайн його гри запозичено з іншої гри, але це не Mined-Out, і він не пам'ятає, яка це була гра.

Ігровий процес

Сапер — відеогра-головоломка. У грі міни (які в класичній темі нагадують морські міни) розкидано по дошці, яка поділена на комірки. Комірки мають три стани: невідкриті, відкриті та позначені. Невідкрита комірка порожня та доступна для натискання, тоді як у відкритій комірці видно вміст. Позначена комірка — це невідкрита комірка, яку гравець позначив, щоб вказати потенційне місце розташування міни; у деяких реалізаціях клітинки з прапорцями не відкриваються, щоб зменшити ризик випадкового потрапляння на міну.

Гравець вибирає комірку, щоб відкрити її. Якщо він відкриває заміновану комірку, гра закінчується програшем. В іншому випадку у відкритій комірці видно або число, що вказує на кількість мін по діагоналі та/або поруч із нею, або порожню плитку (або «0»; у цьому разі всі сусідні не заміновані комірки автоматично відкриваються). Гравець може позначити комірку прапорцем, якщо вважає, що в цьому місці є міна. Позначені комірки все ще вважаються невідкритими, позначки з них можна зняти. У деяких версіях гри, коли кількість суміжних мін дорівнює кількості суміжних позначених комірок, усі суміжні непозначені невідкриті комірки буде відкрито. Ця дія зветься «кординг» (англ. chording).

Ціль і стратегія

Гра починається, коли гравець вперше вибирає клітинку на дошці. У деяких версіях гри перше клацання гарантовано безпечне; тоді як деякі інші варіанти додатково гарантують, що всі суміжні клітини також безпечні. Під час гри гравець використовує інформацію з відкритих комірок, щоб зрозуміти, які комірки можна безпечно відкрити, щоразу отримуючи більше інформації для розв'язання. Гравцеві також відома очікувана кількість мін, що залишилися не позначеними, розраховна як різниця загальної кількості мін та кількості позначених клітинок (це число може бути від'ємним, якщо поставлено забагато прапорців).

Щоб виграти, необхідно відкрити всі комірки, в яких немає мін, не відкриваючи мін. Рахунку немає, але є таймер, який записує час, витрачений на проходження гри. Складність можна збільшити, додавши міни або збільшивши сітку. Microsoft Minesweeper пропонує три типові конфігурації дошки, зазвичай відомі як початковий, середній і експертний рівень, у порядку зростання складності. Початківцю зазвичай пропонують дошку 8x8 або 9x9, що містить 10 мін, середній рівень — 40 мін на дошці 16x16, а експертний — 99 мін на дошці 30x16, однак це зазвичай можна налаштувати.

• Приклад проходження гри початкового рівня складності (9x9)

Історія

За даними TechRadar, гру «Сапер» створила компанія Microsoft у 1990-х роках, але Eurogamer повідомив, що джерелом натхнення стала «менш відома гра з жорстким дизайном», для ZX Spectrum 1983 року. За словами Ендрю, Microsoft зробила за зразком Mined-Out. Версія Microsoft з'явилася 1990 року у ^[en], поширюваному як частина Windows 3.11. Гру написали Роберт Доннер і Курт Джонсон. Джонсон заявив, що дизайн Microsoft Minesweeper запозичено з іншої гри, але це не Mined-Out, і він не пам'ятає, яка це була гра. 2001 року група під назвою International Campaign to Ban Winmine виступила за те, щоб прибрати з теми гри протипіхотні міни, пояснюючи це тим, що гра «є злочином проти жертв мін». У пізнішій версії «Сапера», включеній до Windows Vista, замість мін пропонуються плитки з квітами.

Гра часто постачається разом із операційними системами та стільничними середовищами (наприклад, IBM (OS/2), Microsoft Windows, KDE, GNOME та Palm OS). Microsoft Minesweeper постачався з Windows до версії Windows 8 (2012). Корпорація Майкрософт замінила це безкоштовною версією гри, яку можна завантажити з Microsoft Store, яку How-To Geek назвали «пронизаною рекламою».

Варіанти

Створено варіанти «Сапера», які розширюють основну ідею та додають нові елементи гри. Minesweeper X — це клон версії Microsoft із покращеною рандомізацією та ширшою статистикою, популярний серед гравців, які грають на швидкість. Arbiter і Viennasweeper — клонами, подібні до Minesweeper X. Crossmines — складніша версія базової ідеї гри, в якій додано пов'язані міни та блоки неправильної форми. BeTrapped — казковий варіант гри. В Інтернеті є кілька прямих клонів Microsoft Minesweeper.

«Сапер» увійшов до RuneScape у вигляді під назвою Vinesweeper. Випуски Pokémon HeartGold і SoulSilver поза Японією містили варіанти ігор «Сапер» і Picross. Відеогра Minecraft випустила версію «Сапера» у першоквітневому оновленні 2015 року. ^{[en] [en]} включає варіант гри під назвою Minehunt, де гравець повинен безпечно перейти з одного кута ігрового поля в інший. Єдина підказка — це кількість мін у квадратах навколо поточної позиції гравця. Пошук Google містить версію «Сапера» як великоднє яйце, доступну за назвою гри.

Варіант ^[en], придатний для гри на папері, починається з уже відкритих квадратів. Гравець не може відкрити більше квадратів, натомість має правильно позначити міни, що залишилися. На відміну від звичайної форми «Сапера», ці головоломки зазвичай мають унікальний розв'язок. Ці головоломки з'явилися під назвою «tentaizu» (яп. 天体図, кириліз.: тентайдзу; в перекладі з японської — зоряна карта) в журналі Spirit компанії Southwest Airlines у 2008—2009 роках.

• Головоломка тентайзу
• Онлайновий, не прямокутний
• Тривимірний
• Із шестикутників
• З трикутників
• Декілька мін у комірці
• Емодзі

Змагальна гра

Під час змагань гравці в «Сапера» прагнуть завершити гру якомога швидше. Щоб скоротити час, вони запам'ятовують шаблони. Деякі гравці використовують техніку під назвою «1,5 клацання» (англ. 1.5 click), яка допомагає розкривати міни, тоді як інші гравці взагалі не позначають міни. З гри проводяться турніри. Виникла спільнота відданих гравців, зосереджена на таких вебсайтах, як Minesweeper.info. Станом на 2015 рік, згідно з Книгою рекордів Гіннеса, найшвидше проходження всіх трьох рівнів у «Сапері» становить 38,65 секунди (Каміла Муранський, 2014 рік).

Обчислювальна складність

2000 року Річард Кей опублікував доведення NP-повноти задачі з визначення, чи для даного поля із розкритих (з відомими мітками), правильно позначених і невідомих комірок, існує розташування мін, можливе в межах правил гри. Зрозуміло, що метод швидкого перетворення будь-якої ^[en] на таке поле існує тоді й лише тоді, коли схема є ^[en]; NP-повнота встановлюється за допомогою схеми розміщення мін. Однак якщо поле «Сапера» гарантовано правильне, невідомо, чи задача його розв'язання є NP-повною, але доведено, що вона є co-NP-повною. Однак в останньому випадку «Сапер» демонструє фазовий перехід, аналогічний k-SAT: коли заміновано більш як 25 % квадратів, розгадування дошки вимагає вгадування експоненціально малоймовірного набору мін. Кей також довів, що нескінченний «Сапер» є повним за Тюрінгом.

Див. також

• Tilesweeper

Примітки

1. Edwards, Benj. 30 Years of 'Minesweeper' (Sudoku with Explosions). How-To Geek (амер.). Процитовано 2 серпня 2022.
2. How To Play Minesweeper. Authoritative Minesweeper (англ.). Архів оригіналу за 12 червня 2022. Процитовано 22 квітня 2022.
3. Minesweeper Strategy - First Click. Authoritative Minesweeper (англ.). Архів оригіналу за 2 квітня 2022. Процитовано 2 квітня 2022. Windows Vista introduced guaranteed openings [a cell with no adjacent mines] on the first click...
4. Leonhard, Woody (19 серпня 2009). Windows 7 All-in-One For Dummies. John Wiley & Sons. ISBN .
5. Kaye, Richard (March 2000). Minesweeper is NP-complete!. Mathematical Intelligencer. 22: 9—15. doi:10.1007/BF03025367. ISSN 1866-7414.
6. Cobbett, Richard (5 травня 2009). The most successful game ever: a history of Minesweeper. TechRadar. Архів оригіналу за 13 February 2022. Процитовано 13 лютого 2022.
7. Every step you take: The story of Minesweeper. Eurogamer.net (брит.). 20 липня 2014. Процитовано 24 липня 2022.
8. Blincoe, Robert. Windows Minesweeper is an 'offence to mine victims'. www.theregister.com (англ.). Процитовано 24 липня 2022.
9. Team, Gamesver (10 травня 2022). Minesweeper (Game): 25 Fun / Interesting Facts (History, Stats,…).
10. Edwards, Benj. Every Game Microsoft Ever Included in Windows, Ranked. How-To Geek (амер.). Процитовано 2 серпня 2022.
11. Scullion, Chris (3 лютого 2010). News: Pokémon HeartGold/SoulSilver mini-game revealed! - Official Nintendo Magazine. officialnintendomagazine.co.uk. Архів оригіналу за 6 February 2010. Процитовано 13 січня 2020.
12. Every Minecraft April Fools Joke (Including 2022). ScreenRant. 7 травня 2022.
13. HP 48 Miscellaneous Games. www.hpcalc.org.
14. Sidhwani, Priyansh (6 жовтня 2022). How To Play Google Minesweeper. TechStory (амер.). Процитовано 13 грудня 2022.
15. Minesweeper Puzzles Magazine. www.puzzle-magazine.com.
16. Scott, Allan; Stege, Ulrike; van Rooij, Iris (December 2011). Minesweeper May Not Be NP-Complete but Is Hard Nonetheless. The Mathematical Intelligencer. 33 (4): 5—17. doi:10.1007/s00283-011-9256-x.
17. Dempsey, Ross; Guinn, Charles (2020). A Phase Transition in Minesweeper. arXiv:2008.04116 [cs.AI].
18. Kaye, Richard (31 травня 2007). Infinite versions of minesweeper are Turing complete (PDF). Архів оригіналу (PDF) за 3 August 2016. Процитовано 8 липня 2016.

Література

• (1997). How cellular automaton plays Minesweeper. Applied Mathematics and Computation. 85 (2–3): 127—137. doi:10.1016/S0096-3003(96)00117-8.
• Lakshtanov, Evgeny; Oleg German (2010). Minesweeper and spectrum of discrete Laplacians. Applicable Analysis. 89 (12): 1907—1916. arXiv:0806.3480. doi:10.1080/00036811.2010.505189.
• Mordechai Ben-Ari (2018). Minesweeper is NP-Complete (PDF) (Звіт). Weizmann Institute of Science, Department of Science Teaching. Архів оригіналу (PDF) за 9 червня 2019. — стаття у відкритому доступі, що пояснює результат Кея щодо NP-повноти.

Посилання

• Richard Kaye's Minesweeper pages
• Microsoft Minesweeper playable in the browser on the Internet Archive