Генетические алгоритмы поиска в шахматных программах и нейросетях.

 

 

Альфа-бета алгоритм

В шахматном программировании царит альфа-бета алгоритм поиска лучшего хода. Это оптимизированный перебор для двух сторон на некоторую глубину. Этот алгоритм дает возможность построить шахматную программу базового уровня. Для достижения уровня 1 разряда, мастера и гросса этого мало. Мало потому что дерево поиска растет экспоненциально и чтобы сосчитать поглубже, до 10-12-14 полуходов, нужны эвристики оптимизации поиска.

Недействительное перемещение.

Ключевой эвристикой конца прошлого века стало Недействительное перемещение. Если сторона пропускает ход то это засчитывается как минимум и если минимум уже больше лучшей оценки противника, то дальше можно не продолжать.

Программа Альфа Шахматы

Программа Альфа Шахматы использовала нейросети для оценки позиции, и метод Монте-Карло поиска матовых окончаний. Каждому ходу присваивается оценка для сортировки - случайное число в диапазоне до некоторого значения, выдаваемого нейросетью, ведающей безопасностью короля. Так сделано в Вяленой Рыбе, нынешнем чемпионе.

Генетические алгоритмы

Кроме того, существуют генетические алгоритмы оптимизации поиска где дальше просчитываются только лучшие ходы что повышает вероятность при достижении глубины поиска 12-14 полуходов что программа будет играть в силу гросса.

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

FANTOM CHESS.

 

 

Предлагаю вашему вниманию учебный движок с генетическим алгоритмом. Протокол winboard. Программа скомпилирована для Линукс 64 Дебиан 12. Т е нужен дистрибутив Линукс где компилятор gcc версии такой же или более новый. Мой линукс 2022 года.

Запуск:

sudo apt install xboard

xboard -fcp ./fantom

Ссылка для скачивания:

https://disk.yandex.ru/d/hihWQzhIufBsRA 

Вопросы пожелания по адресу:

evgeniy-korniloff@yandex.ru

 

 

 

Что такое дивергенция

 

Разберу вывод формулы дивергенции — и геометрически, и математически.

Что такое дивергенция

Дивергенция (расходимость) векторного поля $\mathbf{F}=(P,Q,R)$ в точке показывает, насколько поле «расходится» из этой точки — является ли точка источником или стоком.

• Если $\mathrm{div}\mathbf{F}>0$ — точка является источником (поле «вытекает»).

• Если $\mathrm{div}\mathbf{F}<0$ — точка является стоком (поле «втекает»).

• Если $\mathrm{div}\mathbf{F}=0$ — поле соленоидально (нет источников/стоков).

Геометрический вывод (через поток)

Идея: дивергенция — это поток поля через малую замкнутую поверхность на единицу объёма при стягивании поверхности в точку.

Шаг 1. Поток через малый параллелепипед

Возьмём точку (x,y,z) и окружим её малым параллелепипедом со сторонами Δx, Δy, Δz:

(x+Δx, y+Δy, z+Δz)
       +────────────+
      /         /|
     /         / |
    +─────────+  |
    |         |  |
    |         |  + (x, y, z)
    |         | /
    |         |/
    +─────────+

Шаг 2. Вычисляем поток через грани

Поток вектора F через поверхность S определяется как:

$$\Phi ={\iint }_S\mathbf{F}\cdot \mathbf{n}dS,$$

где n — единичная нормаль к поверхности.

Рассмотрим поток через пары противоположных граней:

1. Грани, перпендикулярные оси $Ox$:

• Левая грань (x фиксировано):

  • нормаль: $\mathbf{n}=(-1,0,0)$;

  • поток: $-P(x,y,z)\cdot \Delta y\Delta z$.

• Правая грань ($x+\Delta x$ фиксировано):

  • нормаль: $\mathbf{n}=(1,0,0)$;

  • поток: $P(x+\Delta x,y,z)\cdot \Delta y\Delta z$.

Суммарный поток через эти грани:

$$[P(x+\Delta x,y,z)-P(x,y,z)]\Delta y\Delta z\approx \frac{\partial P}{\partial x}\Delta x\Delta y\Delta z.$$

2. Грани, перпендикулярные оси $Oy$:
Аналогично:

$$[Q(x,y+\Delta y,z)-Q(x,y,z)]\Delta x\Delta z\approx \frac{\partial Q}{\partial y}\Delta x\Delta y\Delta z.$$

3. Грани, перпендикулярные оси $Oz$:

$$[R(x,y,z+\Delta z)-R(x,y,z)]\Delta x\Delta y\approx \frac{\partial R}{\partial z}\Delta x\Delta y\Delta z.$$

Шаг 3. Суммарный поток

Складываем потоки через все грани:

$$\Phi \approx \left(\frac{\partial P}{\partial x}+\frac{\partial Q}{\partial y}+\frac{\partial R}{\partial z}\right)\Delta x\Delta y\Delta z.$$

Шаг 4. Поток на единицу объёма

Объём параллелепипеда: $V=\Delta x\Delta y\Delta z$. Тогда поток на единицу объёма:

$$\frac{\Phi }{V}\approx \frac{\partial P}{\partial x}+\frac{\partial Q}{\partial y}+\frac{\partial R}{\partial z}.$$

При $\Delta x,\Delta y,\Delta z\to 0$ это отношение стремится к дивергенции в точке (x,y,z).

Окончательная формула

Для векторного поля $\mathbf{F}=(P(x,y,z),Q(x,y,z),R(x,y,z))$ дивергенция определяется как:

$$\mathrm{div}\mathbf{F}=\frac{\partial P}{\partial x}+\frac{\partial Q}{\partial y}+\frac{\partial R}{\partial z}.$$

В компактной записи через оператор набла (∇):

$$\mathrm{div}\mathbf{F}=\nabla \cdot \mathbf{F},$$

где $\nabla =\left(\frac{\partial }{\partial x},\frac{\partial }{\partial y},\frac{\partial }{\partial z}\right)$.

Связь с теоремой Гаусса-Остроградского

Теорема связывает поток через замкнутую поверхность с дивергенцией внутри объёма:

$${\iint }_{\partial V}\mathbf{F}\cdot \mathbf{n}dS={\iiint }_V\mathrm{div}\mathbf{F}dxdydz.$$

Левая часть — поток через поверхность ∂V, правая — интеграл от дивергенции по объёму V.

Пример расчёта

Задача: найти дивергенцию поля $\mathbf{F}=(x^2,y^2,z^2)$.

Похоже, вы заметили неполноту в предыдущем ответе про дивергенцию — давайте завершим пример расчёта и разберём ключевые моменты подробнее.

Завершение примера расчёта дивергенции

Задача: найти дивергенцию поля $\mathbf{F}=(x^2,y^2,z^2)$.

Решениение:

• $P=x^2\Rightarrow \frac{\partial P}{\partial x}=2x$;

• $Q=y^2\Rightarrow \frac{\partial Q}{\partial y}=2y$;

• $R=z^2\Rightarrow \frac{\partial R}{\partial z}=2z$.

Тогда дивергенция:

$$\mathrm{div}\mathbf{F}=\frac{\partial P}{\partial x}+\frac{\partial Q}{\partial y}+\frac{\partial R}{\partial z}=2x+2y+2z=2(x+y+z).$$

Интерпретация:

• В точке (0,0,0): $\mathrm{div}\mathbf{F}=0$ — нет источников/стоков.

• В точке (1,1,1): $\mathrm{div}\mathbf{F}=6>0$ — источник.

• В точке (−1,−1,−1): $\mathrm{div}\mathbf{F}=-6<0$ — сток.

---

Дополнительные примеры

Пример 1. Поле скоростей жидкости

Пусть $\mathbf{F}=(x,y,z)$ — поле скоростей. Тогда:

$$\mathrm{div}\mathbf{F}=\frac{\partial x}{\partial x}+\frac{\partial y}{\partial y}+\frac{\partial z}{\partial z}=1+1+1=3.$$

Это означает, что жидкость равномерно «расходится» из каждой точки — есть постоянный источник интенсивности 3.

Пример 2. Соленоидальное поле

Рассмотрим поле $\mathbf{F}=(-y,x,0)$. Вычислим дивергенцию:

$$\mathrm{div}\mathbf{F}=\frac{\partial (-y)}{\partial x}+\frac{\partial x}{\partial y}+\frac{\partial 0}{\partial z}=0+0+0=0.$$

Поле соленоидально — нет источников или стоков (типично для магнитных полей).

---

Физический смысл дивергенции

Представьте векторное поле как поле скоростей течения жидкости:

• $\mathrm{div}\mathbf{F}>0$ — в точке жидкость «вытекает» (источник);

• $\mathrm{div}\mathbf{F}<0$ — жидкость «втекает» (сток);

• $\mathrm{div}\mathbf{F}=0$ — сколько втекает, столько и вытекает (нет источников/стоков).

Аналогия:

• Кран с водой — источник ($\mathrm{div}>0$).

• Слив в раковине — сток ($\mathrm{div}<0$).

• Река без притоков и стоков — соленоидальное поле ($\mathrm{div}=0$).

---

Математические нюансы вывода

Разберу подробнее переход от потока к дивергенции.

Шаг 1. Поток через малый объём

Для параллелепипеда со сторонами Δx, Δy, Δz поток через грани, перпендикулярные оси Ox:

$$[P(x+\Delta x,y,z)-P(x,y,z)]\Delta y\Delta z.$$

При малых Δx это можно приблизить:

$$\approx \frac{\partial P}{\partial x}\Delta x\Delta y\Delta z.$$

Аналогично для других осей.

Шаг 2. Суммарный поток

$$\Phi \approx \left(\frac{\partial P}{\partial x}+\frac{\partial Q}{\partial y}+\frac{\partial R}{\partial z}\right)\Delta x\Delta y\Delta z.$$

Шаг 3. Поток на единицу объёма

$$\frac{\Phi }{V}\approx \frac{\partial P}{\partial x}+\frac{\partial Q}{\partial y}+\frac{\partial R}{\partial z}.$$

Шаг 4. Предельный переход

При $\Delta x,\Delta y,\Delta z\to 0$ отношение VΦ​ стремится к дивергенции в точке:

$$\mathrm{div}\mathbf{F}=\underset{V\to 0}{\lim }\frac{1}{V}{\iint }_{\partial V}\mathbf{F}\cdot \mathbf{n}dS.$$

Это определение дивергенции через поток.

---

Связь с теоремой Гаусса-Остроградского

Теорема утверждает: поток векторного поля через замкнутую поверхность равен интегралу от дивергенции по объёму внутри:

$${\iint }_{\partial V}\mathbf{F}\cdot \mathbf{n}dS={\iiint }_V\mathrm{div}\mathbf{F}dxdydz.$$

Практическое применение:

• Левая часть — вычисление потока через сложную поверхность.

• Правая часть — интегрирование дивергенции (часто проще).

Пример: для поля $\mathbf{F}=(x,0,0)$ и куба [0,1]3:

• Поток через все грани: 1 (только через грань $x=1$).

• Дивергенция: $\mathrm{div}\mathbf{F}=1$.

• Интеграл от дивергенции: ${\iiint }_{V}1dxdydz=1$ — совпадает.

---

Краткий итог

1. Формула дивергенции: $\mathrm{div}\mathbf{F}=\frac{\partial P}{\partial x}+\frac{\partial Q}{\partial y}+\frac{\partial R}{\partial z}$.

2. Физический смысл: показывает интенсивность источников/стоков в точке.

3. Геометрический вывод: основан на вычислении потока через малый параллелепипед и предельном переходе.

4. Теорема Гаусса: связывает поток через поверхность с интегралом от дивергенции внутри.

5. Соленоидальные поля: дивергенция равна нулю (например, магнитное поле).

Хотите, разберу какой‑то аспект подробнее или покажу расчёт для другого векторного поля?