Як легко обіграти у шашки?

Як виграти у шашки

1. Намагайтеся, щоб у вас у дамках було більше шашокніж у противника. …
2. Якомога довше тримайте свої шашки на останньому ряду, не пересувайте їх. …
3. Пересувайте шашки невеликими групами чи парами. …
4. Коли це вигідно вам, обмінюйтесь шашками. …
5. Слідкуйте за центром дошки.

Яка має бути довжина шашки?

Шашка (зброя)

Коли у шашках беруть за Фук?

У шашках "взяти за фук" означало те, що граючий не зробив обов'язкового ходу, не побив шашку супротивника. Натомість він зробив інший хід. При черговому ході супротивник бере цю шашку "за фук".

YouTube
Смішні ідеї з пластикових пляшок. Як зробити шашки із пляшок. Вироби Саморобки своїми руками – YouTube

Мій досвід розробки програми для гри в шашки за допомогою алгоритму мінімакс

В Інтернеті можна відкопати сотні, а в його англомовному сегменті — тисячі, статей про розробку алгоритмів та ІІ для гри в шахи. Однак шашки чомусь не приваблюють такого інтересу. У Рунеті мені не вдалося знайти майже жодної цікавої статті про послідовну розробку алгоритму для гри в шашки, тому мені захотілося створити його самому.

Так як англійські шашки (checkers) вже спіткала нічийна смерть, я вибрав російські шашки, які, до речі, складніші за англійські. Короткі правила та тих та інших наведені нижче:

• Шашки ходять тільки клітинами чорного кольору по діагоналі.
• Проста шашка ходить тільки вперед на одне поле, а б'є вперед і назад, перестрибуючи одне поле (у checkers – б'єтількивперед)
• Жінка ходить і б'є вперед і назад на будь-яку кількість полів (у checkers – ходить вперед і назадтількина 1 полі; б'є, перестрибуючитільки1 поле)
• Бити обов'язково! За наявності кількох варіантів бою можна вибрати будь-який.
• Програє той, хто не може вчинити хід.

Спочатку я хотів писати на python, але потім вирішив зробити гарну круту гру і вибрав Unity (C#). Спойлер: гарної гри я так і не зробив.

Реалізація алгоритму

Вочевидь класи, відповідальні за шашки на екрані й у пам'яті алгоритму, різні. Я не зупинятимуся на MonoBehaviour Unity-скриптах і докладніше розповім саме про мою реалізацію алгоритму.

Спочатку опишу, як я зберігаю дошку у пам'яті.

Клас шашки досить простий: містить, головне, тип шашки та її позицію на полі, а також кілька допоміжних змінних:

public enum PieceType < EMPTY, WHITE_MAN, WHITE_KING, BLACK_MAN, BLACK_KING > public class Piece < public PieceType Type < get; private set; >public Vector2Int Pos < get; private set; >public bool IsWhite < get; private set; >public bool IsKing < get; private set; >public Piece(PieceType type, Vector2Int pos) < Type = type; Pos = pos; IsWhite = type == PieceType.WHITE_MAN || type == PieceType.WHITE_KING; IsKing = type == PieceType.WHITE_KING || type == PieceType.BLACK_KING; >public void ChangePos(Vector2Int newPos) < Pos = newPos; >public void BecomeKing() < Type = IsWhite ? PieceType.WHITE_KING : PieceType.BLACK_KING; IsKing = true; >public void BecomeMan() < Type = IsWhite? PieceType.WHITE_MAN : PieceType.BLACK_MAN; IsKing = false; >>

Думаю, тут коментувати нема чого.

Дошка ж це набір шашок та їх ходів. Це не повний код дошки, а лише важливе:

 public class Board < private Piece [,] _board = New Piece [8, 8]; // фігури public ListPieces <get; private set; >= new List(); // Ті самі фігури, але у вигляді списку private List _currentMoves; // Список можливих ходів private int[] _countCheckers = new int[5]; // лічильник шашок певних груп (всіх, білих звичайних, білих дамок, чорних звичайних, чорних дамок) private List LastMoves = new List(); . // Конструктор для встановлення дошки по рядку // searchAllMoves - чи потрібно шукати можливі ходи public Board (string arr, bool whitesMove = true, bool searchAllMoves = true) < int index = 0; // Прохід всім клітинам for (int y = 0; y < 8; y++) < for (int x = (y+1) % 2; x < 8; x += 2) < if (arr[index] ! = '0') < // Індекс фігури int num = int.Parse(arr[index].ToString()); // Отримуємо фігуру Piece piece = New Piece ((PieceType) num, New Vector2Int (x, y)); // Встановлюємо та заносимо до списків _board[y, x] = piece; Pieces.Add(piece); _countCheckers[num]++; >index++; > > WhitesMove = whitesMove; _rowKingsMoves = 0; _jumpIndex = 0; _countCheckers[0] = _countCheckers[1] + _countCheckers[2] + _countCheckers[3] + _countCheckers[4]; // Якщо потрібно, шукаємо можливі ходи if (searchAllMoves) FindAllMoves(); >. >

• Конструктор Board() тут будує дошку по рядку цифр, де кожна цифра позначає конкретну шашку (див. перелік PieceType в класі Piece).
• Також є конструктор, який створює глибоку копію дошки.

(Розіб'ю весь клас на частини, щоб не було пелени коду і можна було дати пояснення)

Наступні функції використовують для пошуку можливих ходів.

public void FindAllMoves () < ListtakingMoves = new List(); // взяття List simpleMoves = new List(); // Прості ходи foreach (Piece piece in Pieces) < if (piece.IsWhite == WhitesMove) < // Для кожної фігури спочатку шукаємо всі взяття takingMoves.AddRange(GetAllTakingMovesOfPiece(piece)); // Якщо взять немає, шукаємо прості ходи if (takingMoves.Count == 0) simpleMoves.AddRange(GetAllSimpleMovesOfPiece(piece)); >> // Якщо є взяття, відкидаємо прості ходи; інакше є тільки прості ходи if (takingMoves.Count > 0) < // Взяття сортуємо за зменшенням кількості побитих шашок, щоб спочатку йшли найкращі // Це допоможе нам ефективніше шукати найсильніші ходи, оцінюючи потенційно найкращі першими takingMoves.Sort((Move a, Move b) =>-a.Taken.Count.CompareTo(b.Taken.Count)); AllMoves = _currentMoves = takingMoves; > else AllMoves = _currentMoves = simpleMoves; > // Рекурсивна функція пошуку взяття фігури // У масиві exc зберігаються поля, шашки у яких ми вже побили, оскільки у російських шашках, // згідно з турецьким правилом, шашки знімаються з дошки після ходу (див.коментар під кодом) private List GetAllTakingMovesOfPiece (Piece piece, List exc = null) < if (exc == null) exc = new List(); List moves = new List(); // всі взяття List movesWithFollowingTake = new List(); // взяття, після яких можна побити ще if (piece.IsKing) < // Перебираємо всі 4 напрямки руху for (int x = 1; x > -2; x - = 2) < for (int y = 1; y > -2;y -= 2) <bool opp_found = false; Vector2Int pos_opp = Vector2Int.zero; // Куди жінка стане після стрибка Vector2Int target = piece.Pos + new Vector2Int(x, y); while (InField(target)) // Функція InField перевіряє, що координати (x, y) належать полю < if (IsEmpty(target)) // Функція IsEmpty перевіряє, що поле не зайняте < if (opp_found) // Якщо, стрибнувши на клітинку target ми перестрибнемо шашку суперника, це взяття AddMove(piece.Pos, target, pos_opp); // Побічно рекурсивно продовжуємо пошук подальших стрибків з взяттям > else if (_board [target.y, target.x]. IsWhite == piece. IsWhite) // Якщо вперлися в свою шашку – то все break; else < if (!opp_found) // Якщо вперлися в шашку суперника, запам'ятовуємо це < opp_found = true; pos_opp = target; >else// Якщо уткнулися в 2-ю шашку суперника, то далі стрибнути не вийде break; > target += new Vector2Int(x, y); > > > > else < // Тут перебираємо всі 4 варіанти взяття звичайної шашки (для стислості показано тільки одне) // target – поле куди приземлимося, middle – поле, яке перестрибнемо. В даному випадку стрибаємо на збільшення обох координат (вниз праворуч) Vector2Int target = new Vector2Int(piece.Pos.x + 2, piece.Pos.y + 2); Vector2Int middle = new Vector2Int(piece.Pos.x + 1, piece.Pos.y + 1); if (InField(target) && IsEmpty(target) && !IsEmpty(middle) && _board[middle.y, middle.x].IsWhite != piece.IsWhite) AddMove(piece.Pos, target, middle); . . . >if (movesWithFollowingTake.Count > 0) return movesWithFollowingTake; return moves; bool AddMove (Vector2Int fr, Vector2Int to, Vector2Int taken) < // Турецький удар (див.у коментарі нижче) if (exc.Contains(taken)) return false; // Моделюємо дошку, на яку цей хід зроблено Board nextBoard = new Board (this, deepCopyMoves: false); Piece thisPiece = nextBoard.MovePiece(fr, to); ListnewExc = new List(exc); newExc.Add(taken); // Перевіряємо, чи не перетворилася наша шашка в дамку цим ходів bool isThisMoveKinging = !piece.IsKing && IsKinging(to, piece.IsWhite); List nextTakes = nextBoard.GetAllTakingMovesOfPiece(thisPiece, newExc); if (nextTakes.Count == 0) < moves.Add(new Move(new List() < fr, to >, new List() < taken >, isThisMoveKinging)); return false; > else < foreach (Move nextTake in nextTakes) < Listpos = nextTake.Pos; pos.Insert(0, fr); List takes = nextTake.Taken; takes.Add(taken); moves.Add(new Move(pos, takes, isThisMoveKinging || nextTake.IsKinging)); movesWithFollowingTake.Add(new Move(pos, takes, isThisMoveKinging || nextTake.IsKinging)); > return true; > > > // Ця функція шукає всі прості ходи шашки. Вона дуже проста і не представляє особливого інтересу private List GetAllSimpleMoves

• Тут варто звернути увагу на те, що всі звичайні ходи вважаються рівноцінними, а взяття — ні: найсильніші взяття це ті, що б'ють більше за шашки суперника.
• У функції GetAllTakingMoves, яка шукає всі ходи-взяття, важливу роль відіграє т.зв. турецьке правило, згідно з яким побиті шашки знімаються з дошки після ходу і можуть заважати продовжити взяття. Наприклад, у позиції нижче, якщо білі візьмуть дамкою e1:a5:d8:f6:d4, вони не зможуть взяти ще й шашку c5, оскільки, хоча шашка b6 до того часу вже буде побита, вона все ще стоятиме на дошці, мішачись білих.
• У функції AddMove() інтерес також представляє окрема обробка ситуації, коли шашка своїм ходом перетворюється на дамку – у такому разі можна продовжити взяття за її правилами.

Функція MakeMove здійснює хід на дошці:

public void MakeMove(Move move, bool memoriseMove = false) < // Хапоминаем хід, якщо треба if (memoriseMove) LastMoves.Add(new MemorisedMove(move.Fr, move.To, null, move.IsKinging, _rowKingsMoves)); // Рухаємо фігуру (оновлює масив _board і позицію в екземплярі самої фігури // можливо, також перетворює екземпляр фігури в дамку) MovePiece (move.Fr, move.To); // Видаляємо з масивів побиті шашки foreach (Vector2Int taken in move.Taken) <Piece takenPiece=GetPiece(taken); _countCheckers[(int)takenPiece.Type]--; _countCheckers[0]--; Pieces.Remove(takenPiece); _board[taken.y, taken.x] = null; if (memoriseMove) LastMoves[LastMoves.Count - 1].AddTakenPiece(takenPiece); >>

Зрозуміло, це лише основні функції. Повний код, що моніторить дошку, займає майже 500 рядків. Це досить багато, але не думаю, що можна якось поділити відповідальність: все стосується безпосередньо властивостей нинішнього стану гри.

Це все не дуже цікаво, і я навіть міг би знайти та завантажити готовий код шашок у Unity, але я вирішив написати його сам, щоб краще розуміти гру. Можливо, тут можна щось кардинально поліпшити і прискорити.

Перейдемо до цікавіших речей

Розробка переможного алгоритму

Вибраний алгоритм – мінімакс. Це набір правил для прийняття рішень для ігор із нульовою сумою (один виграв – інший програв). Він ґрунтується на тому, щоб для всіх можливих ходів передбачити відповіді суперника, і для кожної відповіді — вибрати свою відповідь, на яку знову передбачити можливі відповіді суперника.

Тобто, ми перебираємо всі варіанти на певну глибину. Зрозуміло, ми не можемо перебрати всі ходи на всю гру, тому дійшовши до максимальної глибини, ми просто аналізуємо отриману позицію і розуміємо, чи варто нам йти в цю гілку гру чи ні. Звичайно, ми в першу чергу розраховуємо, що противник робитиме найсильніші (на нашу думку) ходу.

Якщо кожну позицію оцінити одним числом (наприклад, позитивна перевага у білих, негативна у чорних), то кожної ітерації ми намагаємося максимізувати оцінку позиції, якщо хід наш, і мінімізувати, якщо хід суперника. Справді, якщо позиція покращується для суперника, то вона погіршується для нас. Звідси назва алгоритму – мінімакс.

Мені дуже хочеться назвати це не алгоритмом, а штучним інтелектом, хоча він не є таким. Це тому, що при розробці я назвав клас ІІ і так і продовжував про нього думати, зрозумівши помилку лише пізніше.

Спочатку розберемося, як оцінювати конкретну позицію на дошці, а вже потім вчитиметься думати наперед, оцінюючи отримані позиції.

Клас AI.sc вміє оцінювати позицію, підраховуючи якості шашок обох кольорів на дошці. Якість розраховується як твір вартості шашки, спеціального бонусу клітини (наприклад, шашки в центрі дорожчі за шашки з лівого або правого краю дошки) і Y-бонусу (бонус по вертикалі: проста шашка тим дорожча, чим ближче вона до дамових полів).

Якість шашки = value *_squareBonus * yBonus

Значення цін та бонусів я вибрав такі:

int _checkerValue = 100; // Вартість простої шашки int _kingValue = 250; // вартість короля float[,] _squareBonus = new float[8, 4] // бонус клітини < < 1.2f, 1.2f, 1.2f, 1.2f >, < 1.15f, 1.2f, 1.2f, 1.15f >, <1.15f, 1.2f, 1.2f, 1.13f>, <1.0f, 1.2f, 1.15f, 1.0f>, <1.0f, 1.2f, 1.2f, 1.0f>, <1.0f, 1.0f, 1.0f f, 1.0f >, < 1.0f, 1.0f, 1.0f, 1.0f >, < 1.0f, 1.0f, 1.0f, 1.0f >, >; private float[] _yBonus = new float[8]; // Y-бонус

public float EvaluateMaterialAndPosition (Board board) < float eval = 0; // Розраховуємо якість кожної шашки foreach (Piece piece in board.Pieces) < Vector2Int coord = piece.Pos; switch (piece.Type) < case PieceType.WHITE_MAN: eval += _checkerValue * _yBonus[coord.y] * _squareBonus[coord.y, coord.x/2]; break; case PieceType.BLACK_MAN: eval -= _checkerValue * _yBonus[7 - coord.y] * _squareBonus[7 - coord.y, 3 - coord.x/2]; break; case PieceType.WHITE_KING: eval += _kingValue; break; case PieceType.BLACK_KING: eval -= _kingValue; break; >> return eval; >

Тепер, коли ми вміємо оцінювати позицію, рекурсивно перебиратимемо всі наші ходи, відповіді на них суперника, наші відповіді на відповіді суперника тощо.

Оскільки ми знаємо, наскільки складна нинішня позиція і скільки таких ітерацій потрібно, будемо збільшувати кількість ітерацій, тобто. спочатку проаналізуємо позицію на глибину 2 ходи, потім 4, 6 і т.д. Це називається пошук у глибину з ітеративним поглибленням. При цьому, щоб уникнути нескінченного пошуку, введемо максимальний час аналізу: після його закінчення ми негайно виходимо з усіх функцій і використовуємо результат останньої повністю завершеною ітерації.

// Функція активного пошуку ходу запускає пошук кращого ходу в позиції public void ActiveSearch() < int depth = 0, startDepth = 2; CurrentBestMove = Move.None; // Єдиний позиції хід робиться без роздумів if (_board.AllMoves.Count == 1) < CurrentBestMove = _board.AllMoves[0]; return; >// Робимо копію дошки, де буде проводити аналіз // Це потрібно, оскільки під час аналізу ми пересуватимемо фігури Board boardCopy = new Board(_board, deepCopyMoves: true); _searchStartTime = DateTime.Now; IterativeDeepeningMinimax(boardCopy, _timeLimit, startDepth, ActiveSearchDepth, ref CurrentBestMove, ref depth, true); if (CurrentBestMove == Move.None) CurrentBestMove = boardCopy.AllMoves[new System.Random().Next(0, boardCopy.AllMoves.Count)]; > // Функція мінімаксу з ітеративним поглибленням: запускає мінімакс з дедалі більшою і більшою глибиною, // при цьому стежачи за обмеженням у часі public void IterativeDeepeningMinimax , bool isWhileActiveSearch) < for (depth = minDepth; depth // Якщо не встигли і ітерація завершилася екстрено, вона неповна і її результат нам не потрібен else < depth -= 1; break; >// Ми перестаємо шукати, якщо на якій- то ітерації знайдемо форсований виграш if (eval >= Infinity && board.WhitesMove || eval > // Функція мінімаксу знаходить найкращий хід у позиції за конкретного гравця // Повертає сам хід, а також оцінку позиції, яка вийде, якщо цей хід зробити / / depth показує, наскільки ще ітерацій-рекурсій нам залишилося заглибитися (з кожним новим рекурсивним викликом depth зменшується) // maximizingPlayer показує, якого гравця ми шукаємо кращий хід, тобто.позицію для якого гравця ми намагаємося покращити public (float, Move) Minimax (Board board, int depth, bool maximizingPlayer, float timeLimit) < // Перевірка часу if ((DateTime.Now - _searchStartTime).TotalSeconds >= timeLimit) return (0 , Null); // Перевіряємо нинішній стан позиції (можливо вже гейм овер) GameState state = board.GetGameState(); if (state != GameState.IN_PROCESS) < if (state == GameState.WHITE_WIN) return (Infinity + depth, Move.None); if (state == GameState.BLACK_WIN) return (-Infinity - depth, Move.None); else return (0, Move.None); >// Якщо це остання ітерація, просто повертаємо оцінку позиції // Хід тут не важливий, оскільки найкращим стане саме хід, що веде до позиції з найкращою оцінкою if (depth == 0) < float eval = Evaluate (board); return (eval, Move.None); >// Якщо хід єдиний - див.коментарі під кодом if (board.AllMoves.Count == 1) < Move move = board.AllMoves[0]; board.MakeMove(board.AllMoves[0], memoriseMove: true); board.OnMoveFinished(board.AllMoves[0]); float eval = Minimax(board, depth, alpha, beta, !maximizingPlayer, timeLimit, isWhileActiveSearch).Item1; board.UnmakeLastMove(); _transpositions.Add(new Transposition(PositionCache, eval, Infinity, board.AllMoves[0]))); return (eval, board.AllMoves[0]); >// Шукаємо найкращий хід (за білих) Move bestMove = Move.None; if (maximizingPlayer) < float maxEval = -Infinity; // Проходимося по всіх ходах foreach (Move move in board.AllMoves) < // Робимо його board.MakeMove(move, memoriseMove: true); board.OnMoveFinished(move); // І запускаємо мінімакс з отриманої позиції, але з боку ПРОТИВНИКА (float eval, Move compMove) = Minimax (board, depth - 1, alpha, beta, false, timeLimit, isWhileActiveSearch); // Скасуємо зроблений хід board.UnmakeLastMove(); // Перевірка, що мінімакс із боку противника не завершився екстрено через брак часу if (compMove == null) return (0, null); // Перевіряємо, чи є цей хід кращим за найкращий знайдений if (eval >maxEval) < maxEval = eval; bestMove = move; >> return (maxEval, bestMove); > // Аналогічно за чорних else <float minEval = Infinity; foreach (Move move in board.AllMoves) < board.MakeMove(move, memoriseMove: true); board.OnMoveFinished(move); (float eval, Move compMove) = Minimax(board, depth - 1, alpha, beta, true, timeLimit, isWhileActiveSearch); board.UnmakeLastMove(); if (compMove == null) return (0, null); if (eval <minEval) <minEval = eval; bestMove = move; >> return (minEval, bestMove); > >

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

Я вважаю дуже важливим тут те, що я не копіюю дошку, щоб проаналізувати кожен хід: ВЕСЬ пошук кращого ходу виконується на однієї дошці (копії ігрової), ми вміємо здійснювати (make) і скасовувати ходи (unmake). Таким чином, важка функція глибокого копіювання дошки викликається лише один раз.

В цілому, такий код вже здатний грати і навіть не позіхати фігури в один-два ходи!

Поліпшення №1: alpha-beta pruning

Першим покращенням, яке в рази покращило швидкість аналізу, стало альфа-бета відсікання.

Його суть полягає в тому, що, наприклад, передбачаючи перебіг противника, ми навіть не розглядатиме відверто дурні ходиякі він не зробить. Ну, тобто він, звичайно, може їх зробити, але якщо вони дурні — то нам же краще!

Наприклад, на малюнку нижче ми (граючи за максимізуючу оцінку сторону (за білих)), прорахувавши перші 2 варіанти ходу, бачимо, що можемо отримати позицію з оцінкою 6. Тому коли ми розраховуємо третій хід і бачимо, що одна з його подальших гілок призводить до позиції з оцінкою 5, то далі ми навіть не розраховуємо, тому що навіть якщо там і буде щось вище, суперник краще вибере 5адже він — мінімізуюча сторона (чорні). А тому ми навіть не далі аналізуватимемо 3-ю гілку, адже краще просто піти по 2-й.

Таким чином, ми можемо відсікти (prune) багато зайвих гілок, позбавившись від заздалегідь непотрібних обчислень. В інтернеті багато інформації про це покращення, тому я не далі його розжовуватиму, просто скажу, як я його реалізував.

Функції мінімакс я додав аргументи alpha і beta, які за першого виклику з IterativeDeepeningMinimax передаються як -Infinity і Infinity відповідно.

Після 115-го рядка я додав перевірку на відсікання по альфі:

. alpha = Mathf.Max (alpha, eval); if (beta 

. beta = Mathf.Min (beta, eval); if (beta 

Поліпшення №2: транспозиції

Під час прорахунку позицій часто виникають однакові позиції. Зрозуміло, немає сенсу розраховувати їх знову і знову в різних гілках мінімаксу, а тому ми можемо зберігати якось знайдений кращий хід позиції.

Варто розуміти, що якщо позиції X на глибині d знайдено кращий хід n, то цей же хід є кращим в тій же позиції і на глибинах менше d. А ось на глибинах більше d — не факт: можливо, нам здавалося, що він найкращий, але ми просто не дорахували і насправді програючий хід. Якщо ж у позиції X хід n веде до форсованої перемоги, то глибину можна вважати нескінченною, оскільки ми точно знаємо, що хід виграє.

Позиції вважаються однаковими, якщо не лише всі шашки стоять на однакових місцях, а й черговість ходу збігається.

Транспозиції зберігатимуться у списку private List _transpositions = new List();

Де клас транспозиції виглядає так:

public class Transposition < public string Pos < get; private set; >public float Eval < get; private set; >public int Depth < get; private set; >public Move BestMove < get; private set; >public Transposition(string pos, float eval, int depth, Move bestMove) < Pos = pos; Eval = eval; Depth = depth; BestMove = bestMove; >public bool IsSameTo (string otherPos) => Pos == otherPos; >

На початку функції Minimax() (після, звичайно, перевірки на закінчення часу) перевірятимемо, чи не зустрічали ми раніше цю позицію на відповідній глибині:

string PositionCache = board.Board2Number(); // Перекладає позицію у рядок Transposition pos_trans = null; pos_trans = _transpositions.FirstOrDefault(tr => tr.IsSameTo(PositionCache)); if (pos_trans != null) < if (pos_trans.Depth >= depth) < return (pos_trans.Eval, pos_trans.BestMove); >>

Позиції, до речі, порівнюються як рядки, т.к. кожну позицію можна однозначно подати як рядок із 32 символів – фігур на чорних полях (+1 символ для черговості ходу).

Якщо ж транспозиція не знайдена, запускаємо звичайний пошук. Коли ми завершуємо цикл, перед тим як винести рішення щодо позиції, додаватимемо її до списку транспозицій, як внесок у майбутнє:

// за білих AddTransposition(new Transposition(PositionCache, maxEval, depth, bestMove)); return (maxEval, bestMove);

// за чорних AddTransposition(new Transposition(PositionCache, minEval, depth, bestMove)); return (minEval, bestMove);

Функція AddTransposition просто додає транспозицію до списку, не забуваючи переконатися, що там уже немає такої самої позиції, але на меншій глибині. У такому разі вона стирається, бо навіщо нам менш глибокий аналіз, якщо вже настиг глибший?!

Отже, це покращення дозволяє вичавити ще більше швидкості з нашого алгоритму.

Поліпшення №3: книга дебютів та ендшпилів

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

До речі, з цієї причини саме в ендшпілях транспозиції стають дуже актуальними і корисними.

На жаль, мені не вдалося знайти якихось величезних дебютних та ендшпильних баз даних для шашок, хоча для таких шахів існують, причому можуть займати петабайти даних.

Однак мені вдалося знайти стандартизовані записи шашкових партій і вивудити з них дебюти та ендшпілі (кілька перших ходів з кожної партії та кілька останніх). Тому я підключаю до свого алгоритму два блоки:

private OpeningBook _openingBook; private EndgameBook _endgameBook;

Класи OpeningBook і EndgameBook успадковуються від абстрактного TheoryBook, який вміє шукати цю позицію в довіднику та повертати найкращий у ній хід:

public abstract class TheoryBook < protected abstract string TheoryPath < get; >private BookRecord _records; public TheoryBook() < Debug.Log(TheoryPath); using (StreamReader reader = новий StreamReader(TheoryPath)) < _records = JsonUtility.FromJson(reader.ReadToEnd()); > _records.BuildUpDictionary(); > public bool TryGetBestMove(string pos, out string move) < if (_records.ContainsPosition(pos)) < move = _records.GetMoveFor(pos, BookRecord.BookMoveSelector.Random); return true; >else <move = null; return false; >> > [System.Serializable] public class BookRecord < public Listpositions; public List moves; public int CountRecords => moves.Count; private Dictionary _pairs; public enum BookMoveSelector < Random, First, Last >public BookRecord() < positions = new List(); moves = new List(); > public void AddRecord(string pos, string move) < positions.Add(pos); moves.Add(move); >public void BuildUpDictionary() < _pairs = new Dictionary(); for (int i = 0; i < CountRecords; i++) < if (_pairs.ContainsKey(positions[i])) _pairs[positions[i]].Add(moves[i]); else _pairs.Add(positions[i], new List() < moves[i] >); > > public bool ContainsPosition(string pos) < return _pairs.ContainsKey(pos); >public string GetMoveFor(string pos, BookMoveSelector selector) < switch (selector) < case BookMoveSelector.Random: return _pairs[pos][new System.Random().Next(0, _pairs[pos].Count)]; case BookMoveSelector.First: return _pairs[pos][0]; case BookMoveSelector.Last: return _pairs[pos][_pairs[pos].Count - 1]; default: return _pairs[pos][0]; >> >

Тепер наша програма вміє робити перші 4-5 ходів моментально, доки у неї не закінчиться теорія.

На жаль, вибірка партій була дуже маленькою (кілька тисяч), а й ендшпілі, і особливо дебюти в ній повторювалися, тому дуже сильного приросту якості гри це не дало. Знайти ж велику вибірку чи готові бази мені не вдалося.

Аналіз результатів

Ми отримали програму для гри в російські шашки.

Особисто мене вона розносить в пух і порох (можливо, тому що ще за пару місяців до початку розробки я не вмів нормально грати в шашки і позіхав фігури кожен хід). Я також дав їй зіграти з деякими програмами в плеймаркеті і вона обіграє багато з них на більшості рівнів складності. Воно також обіграє любителів у додатку Quick Checkers.

Розробляючи алгоритм та його поліпшення, я ґрунтувався на статтях про розробку програм для шахів. Саме тому мені довелося самому будувати функцію оцінки позиції, і вона може бути неточною.

Наприклад, можливо, відношення вартості звичайної шашки до дами має бути не 100:250, а 100:150 або 100:500. Можливо, стояти в центрі, а не на краю шашкам вигідніше не в 1.25 рази, а в 1.1 чи 1.5.

Можливо, можливо.

Зрозуміло, це все можна налаштувати, якщо реалізувати "турнір" між комп'ютерами та поступово мутувати ці числа, проте щоб програма могла адекватно грати, їй потрібно 10-15 секунд на КОЖНИЙ ХІД (що дає глибину аналізу 9-10 ходів уперед). Так як у шашкової партії в середньому ходів 30, одна така партія може зайняти 5-8 хвилин, А щоб побудувати нормальний процес мутаційної еволюції потрібно організувати, мабуть, сотні та тисячі партій.

Сподіваюся, комусь мій досвід виявиться корисним та цікавим. Самому мені також цікава ця тема, тому буду радий, якщо в коментарях знайдуться знаючі люди, які зможуть підказати інші можливі покращення та прискорення алгоритму. Я також не заперечую, Що певна стеля швидкості може задавати Unity, так як, швидше за все, на чистому C++ алгоритм працюватиме швидше, ніж на Unity+C#, але переписувати все на С++ я не хочу, до того ж я не знайомий із графічними бібліотеками С++, щоб виводити все це на екран.

P.S. Пропозиціям радий, звичайно, всім, але щось вищематематичне навряд чи зможу продати. Рівень просунутої шкільної математики:)