Рух Короля в шахах

 

 

1ВСТУП

 

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

Історія шахових машин старша, ніж історія  комп'ютерів. Ідея створити машину, що грає в шахи, датується ще вісімнадцятим  століттям. Близько 1769 р. з'явився шаховий автоматМеханічний турок. Він був призначений для розваги королеви Марії Терезії. Машина дійсно непогано грала — усередині неї сидів сильний шахіст, який і робив ходи.

Дослідження механічних шахових автоматів припинилися  з появою цифрових комп'ютерів близько 1950 р. У 1951 р. Алан Турінг написав алгоритм, за допомогою якого машина могла  б грати в шахи, тільки в ролі машини виступав сам винахідник.

В 1957 році було створено першу програму для  гри на стандартній шахівниці  і за участю всіх фігур. Машина прораховувала  на 4 напівходи за 8 хвилин.

Першою  ж машиною, яка досягла рівня  шахового майстра, була Belle, закінчена  в 1983 р Джо Кондоном та Кеном Томпсоном. «Belle» був першим комп'ютером, який проектували тільки для гри в  шахи.

У 1994 Гаррі  Каспаров програв програмі Fritz 3 турнірну бліц партію в Мюнхені. Програма також  виграла у Вішванатана Ананда, Бориса Гельфанда і Володимира Крамника. Гросмейстер Роберт Хюбнер відмовлявся  грати проти програми і автоматично  програв. Каспаров зіграв другий матч із Фріцом і переміг з 4 виграшами  і 2 нічиїми.

На сьогоднішній день перші місця в усіх рейтингах  серед шахових програм посідає  проект Роберта Гударта – Houdini. В 2010 р. ця програма обігнала попереднього чемпіона  Rybka.

Алгоритми в програмних шахах досить громіздкі. Вони розкладають всі можливі  шахові ходи на ієрархічну (деревоподібну) структуру. І аналізують  

раціональні ходи з певною глибиною. Які ходи потрібно аналізувати, а які відкидати  кожен алгоритм відбирає по різному.

Задача  даного курсового проекту проаналізувати один рівень такого дерева. В даному випадку необхідно проаналізувати всі можливі ходи короля, а для  цього потрібно врахувати усі  можливі ходи інших фігур.

Об’єктно-орієнтоване  програмування дозволитьвідділити частину аналізу від інтерфейсної частини. Усю логіку можна виділити в окремий клас.

 

 

2 АНАЛІЗ  ПРЕДМЕТНОЇ ОБЛАСТІ

 

2.1. Обґрунтування аналізу предметної  області

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

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

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

• Випадкова комбінація;
• Розстановка шахів вручну;
• Завантаження файлу з комбінацією;
• Повернення до початкової розстановки.

Випадкова комбінація полягає в  розстановці довільних фігур  на довільні координати. При цьому  певних правил потрібно дотримуватись:

• Король не може стояти на битому полі не в свою чергу ходу, така ситуація неможлива теоретично;
• Жоден пішак не може знаходитись на полі з Y-координатою 1 або 8, адже на початку гри пішаки стоять на полях з Y=2, ходять лише вперед, а дійшовши до поля з Y=8замінюються на будь-яку фігуру;
• Якщо будь-яка фігура може бути виставлена на дошку, а може й ні, то королі виставляються обов’язково;
• Якщо в якась сторона має два слона, то вони мають стояти на клітинках різного кольору, адже на початку гри вони стоять на клітинках різного кольору, а рухаються лише по діагоналі;
• Пішаки можуть знаходитись лише на тих позиціях, на які згідно правил їх ходу вони могли б попасти. Наприклад, неможлива ситуація наведена на рисунку 2.1 (пішак з координатами D3 не міг теоретично там опинитись в даній ситуації).

 

Рисунок 2.1 – Приклад неможливого  розташування пішаків

 

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

• Чергу ходу виставляє користувач, але король не може знаходитись під шахом не в свій хід;
• Королі повинні бути розставлені обов’язково, усі інші фігури можна не ставити.

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

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

 

 

Програма повинна мати меню, мінімальний  склад якого такий:

• Авторська заставка;
• Робота програми;
• Відомості про програму (інструкція);
• Вихід.

 

2.2. Обгрунтування вибору мови

Основні вимоги до мови і середовища програмування наступні:

• Мова повинна бути об’єктно-орієнтованою, оскільки програма громіздка і реалізувати її на мові процедурного програмування було б важко і не по сучасному;
• Мова повинна підтримувати використання готових компонентів та мати потужну їх бібліотеку;
• Бібліотека цих компонентів повинна бути орієнтована на операційну систему Windows.

Усім цим вимогам відповідає мова програмування C# таплатформа.NET.

C#— об'єктно-орієнтована мова  програмування з безпечною системою  типізації для платформи .NET. Розроблена  Андерсом Гейлсбергом, Скотом  Вілтамутом та Пітером Гольде  під егідою Microsoft Research (при фірмі  Microsoft).

Синтаксис C# близький до С++ і Java. Мова має строгу статичну типізацію, підтримує  поліморфізм, перевантаження операторів, вказівники на функції-члени класів, атрибути, події, властивості, винятки, коментарі у форматі XML. Перейнявши багато що від своїх попередників — мов С++, Delphi, Модула і Smalltalk —  С#, спираючись на практику їхнього  використання, виключає деякі моделі, що зарекомендували себе як проблематичні  при розробці програмних систем, наприклад  множинне спадкування класів (на відміну  від C++).

C# є дуже близьким родичем  мови програмування Java. Мова Java була  створена компанією Sun Microsystems, коли  глобальний розвиток інтернету  поставив задачу роззосереджених  обчислень. Взявши за основу  популярну мову C++, Java виключила з  неї потенційно небезпечні речі (типу вказівників без контролю  виходу за межі). Для роззосереджених  обчислень була створена концепція  віртуальної машини та машинно-незалежного  байт-коду, свого роду посередника  між вихідним текстом програм  і апаратними інструкціями комп'ютера  чи іншого інтелектуального пристрою.

Java набула чималої популярності, і була ліцензована також і  компанією Microsoft. Але з плином  часу Sun почала винуватити Microsoft, що  та при створенні свого клону  Java робить її сумісною виключно  з платформою Windows, чим суперечить  самій концепції машинно-незалежного  середовища виконання і порушує  ліцензійну угоду. Microsoft відмовилася  піти назустріч вимогам Sun, і  тому з'ясування стосунків набуло  статусу судового процесу. Суд  визнав позицію Sun справедливою, і зобов'язав Microsoft відмовитися від  позаліцензійного використання Java.

У цій ситуації в Microsoft вирішили, користуючись своєю вагою на ринку, створити свій власний аналог Java, мови, в якій корпорація стане повновладним господарем. Ця новостворена мова отримала назву C#. Вона успадкувала від Java концепції віртуальної  машини (середовище .NET), байт-коду (MSIL) і  більшої безпеки вихідного коду програм, плюс врахувала досвід використання програм на Java.

Нововведенням C# стала можливість легшої взаємодії, порівняно з мовами-попередниками, з кодом програм, написаних на інших мовах, що є важливим при  створенні великих проектів. Якщо програми на різних мовах виконуються  на платформі .NET, .NET бере на себе клопіт щодо сумісності програм (тобто типів  даних, за кінцевим рахунком).

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

C# розроблявся як мова програмування  прикладного рівня для CLR і,  як такий, залежить, перш за  все, від можливостей самої  CLR. Це стосується, перш за все,  системи типів C#. Присутність  або відсутність тих або інших  виразних особливостей мови диктується  тим, чи може конкретна мовна  особливість бути трансльована  у відповідні конструкції CLR. Так,  з розвитком CLR від версії 1.1 до 2.0 значно збагатився і сам  C#; подібної взаємодії слід чекати  і надалі.CLR надає C#, як і всім  іншим .NET-орієнтованим мовам,  багато можливостей, яких позбавлені  «класичні» мови програмування.  Наприклад, збірка сміття не  реалізована в самому C#, а проводиться  CLR для програм, написаних на C# точно так, як і це робиться  для програм на VB.NET, J# тощо

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3 ПРОЕКТУВАННЯ  ПРОГРАМНОГО БЛОКУ

 

3.1Об’єктно-орієнтована модель  програми

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

Програма реалізована мовою  C#, тому є об’єктно-орієнтованою. Одразу після створення проекту в ньому буде два класиProgram–головний клас програмита Form1 –клас головної форми (головного вікна).

Всю логічну частину програми реалізовано  в класі chess, детальний опис якого наведено нижче. Структурну схему класів програми наведено на рисунку 3.1

Рисунок 3.1 – Структура класів програми

 

На схемі класи Legendі about_program – класи вікна умовних позначень та вікна «Про програму» відповідно. До логіки роботи ці класи відношення не мають. Класи panel і actionрозроблені з ціллю спростити керування деякими елементами форми. До логіки роботи також не мають відношення.

 

 

 

3.2 Логіка роботи

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

Рисунок 3.2 – Структура класу chess

 

Поля (змінні) класу chess:

• board – двовимірний цілочисельний масив 8 на 8– зберігає всі фігури розташовані на шаховій дошці. Кожен елемент може приймати значення від 0 до 32. Кожне число позначає фігуру, що знаходиться у відповідному місці дошки. При чому, парні числа позначають чорних, непарні – білих, 0 означає пусте поле. Загальний перелік позначень фігур числами наведений в таблиці 3.1.
• figuresNumber – цілочисельниймасив на 12 елементів– містить інформацію про кількість фігур кожного типу на дошці. Відповідність номера елемента масива виду фігур наведено в таблиці 3.1.Підрахунок фігур потрібен для контролю їх кількості при розстановці вручну;
• figuresNumberMax – також цілочисельний масив на 12 елементів, але заповнений незмінними значеннями відповідно до максимальної кількості фігур;
• fieldsWhite – цілочисельний масив 8 на 8 – відображає всі можливі ходи, биті та криті поля за білою стороною. Кожен елемент може набувати значення від 0 до 6. Їх розшифровку наведено в таблиці 3.2.
• fieldsBlack – аналогічний масив для чорних;
• moveSideWhite – булева змінна – приймає значення true, якщо хід білих. Якщо хід чорних – false;
• check – булева змінна – приймає значення true, якщо є шах королю. Сторона, якій поставили шах визначається з поля moveSideWhite (та, чий хід);
• figure – масив об’єктів внутрішньог класу figures. Кожен елемент (кожна фігура) містить інформацію про свої координати на дошці, свій ID (відповідно до таблиці 3.1), про зображення, яким вона позначаєтсья, про всі поля, які вона контролює (відповідно до таблиці 3.2), та прапор присутності (true, якщо фігура присутня на дошці). Детальніше клас figuresописаний нижче;
• Board –посилання на об’єкт System.Windows.Forms.Panelв головній формі, необхідне для доступу до цього об’єкту з класу chess;
• selected – зберігає номер фігури (відповідно до таблиці 3.1), яку користувач виділив, щоб переставити або подивитись можливі ходи.