English draughts ( британский английский ) или checkers ( американский английский ), также называемые straight checkers или просто draughts , [примечание 1] — это форма стратегической настольной игры checkers (или draughts). Игра ведется на шахматной доске 8×8 с 12 фигурами на каждой стороне. Фигуры двигаются и делают захваты по диагонали вперед, пока не достигнут противоположного конца доски, где они становятся коронованными и после этого могут двигаться и делать захваты как вперед, так и назад.
Как и во всех видах шашек, в английских шашках играют два противника, которые поочередно ходят по разные стороны доски. Фигуры традиционно черные, красные или белые. Фигуры противника захватываются путем перепрыгивания через них.
Вариант шашек 8×8 был слабо решен в 2007 году командой канадских компьютерных ученых под руководством Джонатана Шеффера . Из стандартной начальной позиции оба игрока могут гарантировать ничью при идеальной игре .
Хотя традиционно фигурки изготавливаются из дерева, сейчас многие из них сделаны из пластика, хотя могут использоваться и другие материалы. Фигурки обычно плоские и цилиндрические . Они неизменно разделены на один более темный и один более светлый цвет. Традиционно и на турнирах эти цвета красный и белый, но в Соединенных Штатах распространены черный и красный, а также темные и светлые деревянные фигурки. Более темная сторона обычно называется «черной», а более светлая — «белой».
Существует два класса фигур: люди и короли . Люди — это отдельные фигуры. Короли состоят из двух людей одного цвета, поставленных друг на друга. Нижняя фигура называется коронованной . В некоторых наборах есть фигуры с короной, отформованной, выгравированной или нарисованной с одной стороны, что позволяет игроку просто перевернуть фигуру или положить ее на коронованного человека стороной с короной вверх, что еще больше отличает королей от людей. Фигуры часто изготавливаются с углублениями для облегчения укладки.
Каждый игрок начинает с 12 фишек на темных клетках трех рядов, ближайших к стороне этого игрока (см. схему). Ряд, ближайший к каждому игроку, называется королевским рядом или короной . Игрок с фишками более темного цвета ходит первым. Затем ходы ходят по очереди.
В английских шашках есть два разных способа хода:
Прыжки всегда обязательны: если у игрока есть возможность прыгнуть, он должен ею воспользоваться, даже если это приведет к невыгодному положению для прыгающего игрока. Например, обязательный одиночный прыжок может настроить игрока так, что у противника будет возможность сделать многократный прыжок в ответ.
Возможны множественные прыжки , если после одного прыжка другая фигура сразу же может быть перепрыгнута перемещенной фигурой, даже если этот прыжок в другом диагональном направлении. Если доступно более одного множественного прыжка, игрок может выбрать, с какой фигурой прыгать и какую последовательность прыжков делать. Выбранная последовательность не обязательно должна быть той, которая максимизирует количество прыжков за ход; однако игрок должен совершить все доступные прыжки в выбранной последовательности.
Если фигура перемещается в королевский ряд на стороне доски противника, она коронуется как король и получает возможность ходить как вперед, так и назад. Если фигура перемещается в королевский ряд или прыгает в королевский ряд, текущий ход заканчивается; фигура коронуется как король, но не может выпрыгнуть обратно, как в мультипрыжке, до следующего хода.
Игрок выигрывает, захватывая все фигуры противника или не оставляя противнику возможности сделать ход. Игра заканчивается вничью, если ни одна из сторон не может добиться победы, или по соглашению (одна сторона предлагает ничью, другая принимает).
В выпуске журнала English Draughts Association Journal за декабрь 1977 года было опубликовано письмо Алана Бекерсона из Лондона, который обнаружил ряд полных партий длиной в двадцать ходов. Это были самые короткие партии, когда-либо обнаруженные, и Алан получил место в Книге рекордов Гиннесса. Он предложил приз в размере 100 фунтов стерлингов любому, кто сможет найти полную партию менее чем за двадцать ходов. В феврале 2003 года Мартин Брайант (автор программы шашек Colossus) опубликовал на своем сайте [1] статью , в которой представил исчерпывающий анализ, показывающий, что существует 247 партий длиной в двадцать ходов (и подтвердил, что это самая короткая возможная партия), приводящая (путем перестановки) к 32 различным финальным позициям.
Существует стандартизированная нотация для записи партий. Все 32 достижимых поля доски пронумерованы последовательно. Нумерация начинается с двойного угла черных (где у черных есть два соседних поля). Поля черных на первом ряду пронумерованы от 1 до 4 ; на следующем ряду от 5 до 8 и так далее. Ходы записываются как «от-до», поэтому ход с 9 на 14 будет записан как 9-14. Взятия отмечаются знаком «x», соединяющим начальное и конечное поля. Результат игры часто сокращается до BW/RW (победа черных/красных) или WW (победа белых).
Белые сдались после 46-го хода черных.
В Unicode черновики кодируются в блоке «Разные символы»:
Чемпионат мира по английским шашкам среди мужчин проводится с 1840-х годов, на несколько десятилетий раньше чемпионата мира по шашкам среди мужчин , чемпионата по международным шашкам среди мужчин. Среди известных чемпионов мира — Эндрю Андерсон , Джеймс Уайли , Роберт Мартинс , Роберт Д. Йейтс , Джеймс Ферри , Альфред Джордан , Ньюэлл У. Бэнкс , Роберт Стюарт , Аса Лонг , Уолтер Хеллман , Мэрион Тинсли , Дерек Олдбери , Рон Кинг , Мишель Боргетти , Алекс Моисеев , Любабало Кондло , [5] Серхио Скарпетта , Патрисия Брин и Амангуль Дурдыева . [6] Чемпионаты проводятся в версиях GAYP (Go As You Please) и 3-Move.
С 1840 по 1994 год победителями среди мужчин были представители Шотландии, Англии и США. С 1994 по 2023 год победителями среди мужчин были представители США, Барбадоса , Южной Африки и Италии.
Женский чемпионат стартовал в 1993 году. По состоянию на 2022 год победительницами среди женщин были представительницы Ирландии, Туркменистана и Украины .
Кубок Европы проводится с 2013 года, чемпионат мира — с 2015 года.
Первая английская программа для шашек была написана Кристофером Стрейчи , магистром наук в Национальной физической лаборатории (NPL) в Лондоне. [7] Стрейчи закончил программу, написанную в свободное время, в феврале 1951 года. Впервые она была запущена на компьютере Pilot ACE Национальной физической лаборатории 30 июля 1951 года. Вскоре он модифицировал программу для работы на компьютере Manchester Mark 1 .
Вторая компьютерная программа была написана в 1956 году Артуром Сэмюэлем , исследователем из IBM . Помимо того, что это была одна из самых сложных игровых программ, написанных в то время, она также хорошо известна как одна из первых адаптивных программ. Она обучалась, играя в игры против измененных версий самой себя, причем победившие версии выживали. Программа Сэмюэля была далека от овладения игрой, хотя одна победа над слепым мастером шашек создала у широкой публики впечатление, что она была очень хороша.
В ноябре 1983 года Научный музей Оклахомы (тогда называвшийся Omniplex) представил новую экспозицию: Lefty, играющий в шашки робот. Запрограммированный Скоттом М. Сэвиджем, Lefty использовал роботизированную руку Armdroid от Colne Robotics и был оснащен процессором 6502 с комбинацией кода BASIC и Assembly для интерактивной игры в шашки с посетителями. Первоначально программа была намеренно простой, чтобы среднестатистический посетитель мог потенциально выиграть, но со временем она была улучшена. Улучшения оказались разочаровывающими для посетителей, поэтому исходный код был переписан. [8]
В 1990-х годах самой сильной программой была Chinook , написанная в 1989 году командой из Университета Альберты под руководством Джонатана Шеффера . Марион Тинсли , чемпион мира с 1955 по 1962 и с 1975 по 1991 год, выиграл матч против машины в 1992 году. В 1994 году Тинсли пришлось уйти в отставку посреди равного матча по состоянию здоровья; вскоре после этого он умер. В 1995 году Chinook защитил свой титул человека-машины против Дона Лафферти в матче из тридцати двух игр. Окончательный счет был 1–0 с 31 ничьей в пользу Chinook над Доном Лафферти. [9] В 1996 году Chinook выиграл в Национальном турнире США с самым большим отрывом за всю историю и был выведен из игры после этого события. С тех пор титул человека-машины не оспаривался.
В июле 2007 года в статье, опубликованной в журнале Science Magazine , разработчики Chinook объявили, что программа была улучшена до такой степени, что она не могла проиграть ни одной партии. [10] Если ни один из игроков не совершал ошибок, игра всегда заканчивалась вничью. Спустя восемнадцать лет они вычислительно доказали слабое решение для игры в шашки. [11] Используя от двухсот настольных компьютеров на пике проекта и около пятидесяти позже, команда провела 10 14 вычислений для поиска из начальной позиции в базе данных позиций с максимум десятью фигурами. [12] Однако решение предназначено только для начальной позиции, а не для всех 156 принятых случайных 3-ходовых дебютов турнирной игры.
Число возможных позиций в английских шашках составляет 500 995 484 682 338 672 639 [13] , а сложность игрового дерева составляет приблизительно 10 40 . [14] Для сравнения, в шахматах, по оценкам, существует от 10 43 до 10 50 допустимых позиций .
Если обобщить шашки так, чтобы в них можно было играть на доске m × n , то задача определения того, выигрывает ли первый игрок в данной позиции, становится EXPTIME-complete .
Заявление команды Chinook в июле 2007 года о том, что игра решена, следует понимать в том смысле, что при идеальной игре с обеих сторон игра всегда заканчивается вничью. Однако не все позиции, которые могли возникнуть из-за неидеальной игры, были проанализированы. [15]
Некоторые ведущие программы по шашкам — Chinook и KingsRow .