Ifrit

История разработки.

на главную страницу

 

Ifrit_C История разработки.
часть 3

Часть 4
_______________________________________________________________________________________________
Пятница, 28 декабря 2007 г.
Во время перерыва в описании добавил хеш-таблицу и нулевой ход. Заработало, точнее, сделало вид что заработало, сразу. Так что описывать нечего.
Решил все модули разбить по следующим папкам. Жаль, что при сохранении на сайте модули валятся кучей. Папки только внутри среды разработки.
0_Program файлы начинаются с a
1_UCI b
2_Go c
3_Generator d
4_Move e
5_Check f
6_Loop g
7_Estimation h
8_Forced i
9_Hash j
10_Util k

Уровень игры Ифрита очень низок. Но, несмотря на это новых методов я добавлять сейчас не буду. Хотя очень хочется добавить киллера и историю. И главное заняться, наконец, этой убогой оценкой. Но я взял себя в руки. Сейчас главное написать тестовые функции. Тестироваться должны все критические места. Причем тестироваться в автоматическом режиме. Кроме того, нужно создать возможность компиляции.
1 полный перебор
2 полный перебор + оценка + вывод варианта
3 полный перебор + оценка + вывод варианта + форсированный вариант
4 полный перебор + оценка + вывод варианта + форсированный вариант + хеш
5 полный перебор + оценка + вывод варианта + форсированный вариант + хеш + нулевой ход

_______________________________________________________________________________________________
Вторник, 8 января 2008 г.
Последнюю неделю плотно занимался программой. Добавил киллеров. Ускорение видно невооруженным взглядом. Добавил сортировку списка ходов в следующем порядке: конь, слон, ферзь, ладья, король, пешки. Из соображения частоты передвижения фигур. Не знаю, как это будет работать. Скажу только то обстоятельство, что пешки в самом конце, в большинстве случаев точно ускорит перебор. Добавил негаскаут. Ускорения почти не видно. Я не пойму, то ли я из альфа беты уже все выжал, то ли просто реализация кривая :) Заметное ускорение обеспечивают: хеш, киллеры, нулевой ход. Переписал оценку позиции. Теперь мы материал считаем в конце форсировок, а позиционный фактор в конце основного перебора. Ускорение заметно. И действительно, зачем считать позиционный фактор в конце разменов? Я все таки думаю, что такой способ является корректным. Продолжил раскидывать функции по тематическим модулям. В результате число модулей растет с устрашающей скоростью :) В оценке ввел штраф за сдвоенные пешки и бреши в щите короля. Добавил возможность при компиляции отключать эвристики. Очень удобно.

Сейчас запас новых идей исчерпан. Ну, разве что сортировку по истории добавить. И все равно прога играет довольно слабо. Глубина должна быть 10-11 а она 7-8. Понятно, что в тактике ее другие проги постоянно переигрывают. Статическая оценка просто убогая. Конечно, уровень игры гораздо выше, чем был до этого, но все равно совершенно недостаточен.

Не будем забывать основную идею этого проекта. Очень мало материала на русском языке. Этот проект как раз направлен на то, что бы показать основные идеи шахматной программы. Все должно быть предельно доступным и все должно работать на практике. Пока что описание, которое я выложил на сайте больше похоже на бред :) Постараюсь исправить ситуацию. Ну и конечно нужно писать тестовые функции. Мы должны быть уверенны, что все работает, так как планировалось.
_______________________________________________________________________________________________
Воскресенье, 13 января 2008 г.

Решил посмотреть на эффективность альфа-беты при различных сортировках все тестируем без форсировок, что бы не было искажений.
FEN: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
Ifrit_C29_3 Debug:

Полный перебор
4/4 00:01 206.603 1 -0,02 Nb1c3 d7d5 Ng1f3 Bc8d7
5/5 00:26 5.072.212 1 +0,88 b2b3 d7d5 Bc1b2 Bc8d7 Bb2xg7
6/6 09:41 124.132.536 1 -0,72 a2a4 g7g6 b2b4 Bf8h6 Nb1c3 Bh6xd2+

Альфа-бета
5/5 00:01 112.914 176.428 +0,88 b2b3 d7d5 Bc1b2 Bc8d7 Bb2xg7
6/6 00:10 1.947.198 213.392 -0,72 a2a4 g7g6 b2b4 Bf8h6 Nb1c3 Bh6xd2+
7/7 01:31 15.780.730 194.260 +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+

---------------------------------------------------
Альфа-бета + сортировка следующем порядке: конь, слон, ферзь, ладья, король, пешки
5/5 00:01 93.656 139.369 +0,88 g2g3 e7e5 Bf1g2 Bf8e7 Bg2xb7
6/6 00:07 1.220.579 187.349 -0,72 a2a4 g7g6 b2b4 Bf8h6 Nb1c3 Bh6xd2+
7/7 00:52 7.739.977 172.360 +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+
8/8 11:43 118.766.171 182.349 -0,77 g2g3 a7a5 Ng1h3 Ra8a6 Bf1g2 Ra6h6 Nh3f4 Rh6xh2

Альфа-бета + сортировка следующем порядке: король, ферзь, ладья, слон, конь, пешки
5/5 00:01 98.298 125.862 +0,88 g2g3 e7e5 Bf1g2 Bf8e7 Bg2xb7
6/6 00:07 1.154.931 176.406 -0,72 a2a4 g7g6 b2b4 Bf8h6 Nb1c3 Bh6xd2+
7/7 00:53 7.842.929 171.783 +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+
8/8 10:55 109.950.220 182.713 -0,77 g2g3 a7a5 Bf1g2 Ra8a6 Nb1c3 Ra6g6 Ng1f3 Rg6xg3

Альфа-бета + сортировка следующем порядке: ферзь, ладья, слон, конь, король, пешки
5/5 00:01 91.991 1 +0,88 g2g3 e7e5 Bf1g2 Bf8e7 Bg2xb7
6/6 00:07 1.096.088 167.829 -0,72 a2a4 g7g6 b2b4 Bf8h6 Nb1c3 Bh6xd2+
7/7 00:49 7.204.299 173.598 +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+
8/8 09:58 100.368.643 182.894 -0,77 g2g3 a7a5 Bf1g2 Ra8a6 Nb1c3 Ra6g6 Ng1f3 Rg6xg3
-------------------------------------------------

Альфа-бета + сортировка по взятиям
6/6 00:05 934.177 183.929 -0,72 a2a4 g7g6 b2b4 Bf8h6 Nb1c3 Bh6xd2+
7/7 00:43 6.561.135 173.304 +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+
8/8 04:56 44.709.148 177.208 -0,77 g2g3 a7a5 Bf1g2 Ra8a6 Nb1c3 Ra6g6 Ng1f3 Rg6xg3

Альфа-бета + сортировка по взятиям + сортировка следующем порядке: ферзь, ладья, слон, конь, король, пешки
6/6 00:04 621.216 165.658 -0,72 a2a4 g7g6 b2b4 Bf8h6 Nb1c3 Bh6xd2+
7/7 00:29 4.112.652 163.181 +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+
8/8 04:31 37.901.135 156.829 -0,77 g2g3 a7a5 Bf1g2 Ra8a6 Nb1c3 Ra6g6 Ng1f3 Rg6xg3

Альфа-бета + киллер
6/6 00:02 368.322 191.635 -0,72 a2a4 g7g6 b2b4 Bf8h6 Nb1c3 Bh6xd2+
7/7 00:15 2.388.106 186.615 +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+
8/8 01:31 14.945.845 196.496 -0,77 g2g3 a7a5 Bf1g2 Ra8a6 Nb1c3 Ra6g6 Ng1f3 Rg6xg3

Альфа-бета + киллер (новая сортировка)
6/6 00:02 348.538 174.269 -0,72 a2a4 g7g6 b2b4 Bf8h6 Nb1c3 Bh6xd2+
7/7 00:16 2.271.275 167.845 +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+
8/8 01:41 15.502.822 182.253 -0,77 g2g3 a7a5 Bf1g2 Ra8a6 Nb1c3 Ra6g6 Ng1f3 Rg6xg3

Альфа-бета + киллер + сортировка по взятиям + сортировка следующем порядке: ферзь, ладья, слон, конь, король,
пешки
6/6 00:02 294.438 168.250 -0,72 a2a4 g7g6 b2b4 Bf8h6 Nb1c3 Bh6xd2+
7/7 00:12 1.787.945 169.779 +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+
8/8 01:35 13.347.944 162.439 -0,77 g2g3 a7a5 Bf1g2 Ra8a6 Ng1h3 Ra6h6 Nh3f4 Rh6xh2

Альфа-бета + киллер (новая сортировка) + сортировка по взятиям + сортировка следующем порядке: ферзь, ладья,
слон, конь, король, пешки
6/6 00:02 276.470 156.552 -0,72 a2a4 g7g6 b2b4 Bf8h6 Nb1c3 Bh6xd2+
7/7 00:13 1.755.783 159.617 +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+
8/8 01:35 12.315.684 150.364 -0,77 g2g3 a7a5 Bf1g2 Ra8a6 Ng1h3 Ra6h6 Nh3f4 Rh6xh2


Альфа-бета + хеш (более глубокие на менее глубокие)
6/6 00:07 1.168.341 189.789 -0,72 a2a4 g7g6 b2b4 Bf8h6 Nb1c3 Bh6xd2+
7/7 00:46 6.886.459 175.518 +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+

Альфа-бета + хеш (менее глубокие на более глубокие)
6/6 00:08 1.197.577 169.580 -0,72 a2a4 g7g6 b2b4 Bf8h6 Nb1c3 Bh6xd2+
7/7 01:10 10.889.548 175.020 +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+


Альфа-бета + хеш (новая сортировка) (менее глубокие на более глубокие)
6/6 00:06 1.157.998 193.516 -0,72 a2a4 g7g6 b2b4 Bf8h6 Nb1c3 Bh6xd2+
7/7 00:45 6.702.890 173.045 +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+

Альфа-бета + хеш + киллер (новая сортировка)
6/6 00:02 382.733 173.654 -0,72 a2a4 g7g6 b2b4 Bf8h6 Nb1c3 Bh6xd2+
7/7 00:13 1.812.299 164.754 +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+
8/8 01:34 14.031.222 173.561 -0,77 g2g3 a7a5 Bf1g2 Ra8a6 Nb1c3 Ra6g6 Ng1f3 Rg6xg3


Альфа-бета + хеш + киллер (новая сортировка) + сортировка по взятиям + сортировка следующем порядке ферзь,
ладья, слон, конь, король, пешки
6/6 00:02 308.901 140.155 -0,72 a2a4 g7g6 b2b4 Bf8h6 Nb1c3 Bh6xd2+
7/7 00:12 1.353.303 140.837 +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+
8/8 01:01 6.926.790 140.600 -0,77 g2g3 a7a5 Bf1g2 Ra8a6 Nb1c3 Ra6g6 Ng1f3 Rg6xg3

Вывод:
При максимальной сортировке мы получили в 23 раза больше узлов, чем при идеальной сортировке.
6.926.790 узлов вместо 297 185 узлов.

Альфа-бета
7/7 01:31 15.780.730 194.260 +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+

Альфа-бета + сортировка в следующем порядке: ферзь, ладья, слон, конь, король, пешки
7/7 00:49 7.204.299 173.598 +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+
8/8 09:58 100.368.643 182.894 -0,77 g2g3 a7a5 Bf1g2 Ra8a6 Nb1c3 Ra6g6 Ng1f3 Rg6xg3

Альфа-бета + сортировка по взятиям
7/7 00:43 6.561.135 173.304 +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+
8/8 04:56 44.709.148 177.208 -0,77 g2g3 a7a5 Bf1g2 Ra8a6 Nb1c3 Ra6g6 Ng1f3 Rg6xg3

Альфа-бета + киллер(новая сортировка)
7/7 00:16 2.271.275 167.845 +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+
8/8 01:41 15.502.822 182.253 -0,77 g2g3 a7a5 Bf1g2 Ra8a6 Nb1c3 Ra6g6 Ng1f3 Rg6xg3

Альфа-бета + хеш(новая сортировка) (менее глубокие на более глубокие)
6/6 00:06 1.157.998 193.516 -0,72 a2a4 g7g6 b2b4 Bf8h6 Nb1c3 Bh6xd2+
7/7 00:45 6.702.890 173.045 +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+

Киллер - это самая мощная эвристика 8 глубина 01:41
Далее сортировка по взятиям (взятия выводим наверх) 8 глубина 04:56
Далее хеш 7 глубина 00:45
Далее сортировка по порядку
ферзь, ладья, слон, конь, король, пешки 7 глубина 00:49


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

Что же можно тут еще сделать? Можно добавить второго киллера и посмотреть ускорит ли это перебор. И нужно плотно поработать с хешем сделать его побольше и ключ 64. Тут тоже надо будет подумать.

_______________________________________________________________________________________________
Понедельник, 14 января 2008 г.

Протестировал негаскаут.

Все тестируем без форсировок что бы не было искажений.
FEN: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
Ifrit_C29_3 Debug:

Альфа-бета + негаскаут
6/6 00:10 1.921.205 193.924 -0,72 a2a4 g7g6 b2b4 Bf8h6 Nb1c3 Bh6xd2+
7/7 01:40 16.028.986 178.815 +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+
Без негаскаута
7/7 01:31 15.780.730 194.260 +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+

Альфа-бета + сортировка по взятиям + сортировка следующем порядке ферзь, ладья, слон, конь,король, пешки +
негаскаут
6/6 00:04 596.695 153.986 -0,72 a2a4 g7g6 b2b4 Bf8h6 Nb1c3 Bh6xd2+
7/7 00:30 4.003.480 153.980 +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+
8/8 03:57 33.902.991 163.734 -0,77 g2g3 a7a5 Bf1g2 Ra8a6 Nb1c3 Ra6g6 Ng1f3 Rg6xg3
Без негаскаута
8/8 04:31 37.901.135 156.829 -0,77 g2g3 a7a5 Bf1g2 Ra8a6 Nb1c3 Ra6g6 Ng1f3 Rg6xg3

Альфа-бета + киллер + негаскаут
6/6 00:03 412.806 167.196 -0,72 a2a4 g7g6 b2b4 Bf8h6 Nb1c3 Bh6xd2+
7/7 00:19 2.622.454 165.194 +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+
8/8 01:52 17.618.387 187.835 -0,77 g2g3 a7a5 Bf1g2 Ra8a6 Nb1c3 Ra6g6 Ng1f3 Rg6xg3
Без негаскаута
8/8 01:41 15.502.822 182.253 -0,77 g2g3 a7a5 Bf1g2 Ra8a6 Nb1c3 Ra6g6 Ng1f3 Rg6xg3

Альфа-бета + хеш + негаскаут
6/6 00:06 1.019.299 183.228 -0,72 a2a4 g7g6 b2b4 Bf8h6 Nb1c3 Bh6xd2+
7/7 00:40 6.136.428 178.597 +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+
Без негаскаута
7/7 00:45 6.702.890 173.045 +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+

Альфа-бета + хеш + киллер(новая сортировка) + сортировка по взятиям + сортировка следующем порядке ферзь,
ладья, слон, конь,король, пешки +негаскаут

6/6 00:03 338.214 133.629 -0,72 a2a4 g7g6 b2b4 Bf8h6 Nb1c3 Bh6xd2+
7/7 00:12 1.390.746 159.801 +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+
8/8 00:55 6.124.158 140.183 -0,77 g2g3 a7a5 Bf1g2 Ra8a6 Nb1c3 Ra6g6 Ng1f3 Rg6xg3
Без негаскаута
8/8 01:01 6.926.790 140.600 -0,77 g2g3 a7a5 Bf1g2 Ra8a6 Nb1c3 Ra6g6 Ng1f3 Rg6xg3

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

Протестировал нулевой ход.

Альфа-бета + нулевой ход
6/6 00:01 164.813 170.261 -0,05 a2a4 Nb8c6 Ng1f3 e7e5 Nb1c3 Bf8e7
7/7 00:04 519.936 174.183 +0,29 Nb1c3 a7a6 a2a3 Ng8f6 e2e4 a6a5 Bf1e2
Без нулевого хода
7/7 01:31 15.780.730 194.260 +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+


Альфа-бета + хеш + киллер(новая сортировка) + сортировка по взятиям + сортировка следующем порядке ферзь, ладья, слон, конь, король, пешки + негаскаут + нулевой ход.

6/6 00:01 66.475 1 -0,05 a2a4 Nb8c6 Ng1f3 e7e5 Nb1c3 Bf8e7
7/7 00:02 99.827 138.841 +0,19 a2a4 Nb8c6 Ng1f3 e7e6 d2d4 Bf8e7 Bc1d2
8/8 00:09 838.007 119.187 -0,03 a2a4 Nb8c6 Nb1c3 Nc6d4 e2e3 Nd4f5 e3e4 Ng8f6
9/9 00:25 2.058.082 127.752 +0,22 e2e4 Nb8c6 Bf1b5 Nc6d4 Bb5e2 Ng8f6 Nb1c3 Nd4xe2 Ng1xe2
10/10 02:49 17.883.526 124.016 +0,14 g2g3 Nb8c6 Bf1g2 Nc6d4 Ng1f3 Nd4xf3+ Bg2xf3 d7d5 00 Bc8d7

Без нулевого хода
6/6 00:03 338.214 133.629 -0,72 a2a4 g7g6 b2b4 Bf8h6 Nb1c3 Bh6xd2+
7/7 00:12 1.390.746 159.801 +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+
8/8 00:55 6.124.158 140.183 -0,77 g2g3 a7a5 Bf1g2 Ra8a6 Nb1c3 Ra6g6 Ng1f3 Rg6xg3

Ускорение от нулевого хода просто потрясающее.
Лля глубины 8 при идеальной сортировке нужно рассмотреть 297 185 узлов мы рассмотрели 838.007 в 2,8 раза больше.

Для глубины 10 при идеальной сортировке нужно рассмотреть 8 478 249 узлов мы рассмотрели 17.883.526 узлов в 2,1 раза больше.

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

Другой вопрос - даст ли нулевой ход прирост при идеальной альфа-бете?

_______________________________________________________________________________________________
Суббота, 3 мая 2008 г.
Как же все-таки определять списки ходов? Очевидно, что лучше один раз создать список и потом с ним работать, чем создавать и уничтожать его в каждом новом узле. Пробовал создавать общий список глобально и в функции различия в скорости я не заметил. Либо это без разницы, либо пока просто не чувствую по причине более крутых тормозов.
_______________________________________________________________________________________________
Среда, 7 мая 2008 г.
Когда остается чистый генератор даже без записи варианта скорость 1,5 миллиона позиций в секунду - это глубина 6 за 1м 19сек. Без детектора шаха - 1,8.
У чемпиона 39 миллиона. Глубина 6 за 3,7 сек. У Греки 23 миллиона. Скорость больше от 26 до 15 раз! Это от 5 до 3 полуходов при идеальной а-б. Приходится признать, что генератор у меня очень медленный. И здесь есть куда стремиться.
_______________________________________________________________________________________________
Вторник, 20 мая 2008 г.
Выпустил «Ифрит б2».
Что-то мне не нравиться как он играет, хотя явных глюков я не вижу. Тем не менее, что-то в нем не так.

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

Форсированные ходы считаются верно, т.е. оценка правильная, а вот вариант, по-моему, не всегда точен. Там что-то было. С этим надо будет разобраться.

Очевидно, что если нет выигрывающих комбинаций, ходы делаются на основании позиционной оценки.

Соответствие оценки позиции варианту у меня тоже проверяется и если есть косяк, сигнал пишется в поток. Кстати, возникла идея сделать звуковой сигнал при ошибке вывода.
_______________________________________________________________________________________________
Среда, 21 мая 2008 г.
Альфа-бета содержит в себе засаду. Дело в том, что варианты после лучшего не достоверны. Они слишком оптимистичны для ходящей стороны. Идея тут такая - раз они все равно будут отброшены, уточнять их не надо. Мы находим нижнюю планку для ответа противника и на этом останавливаемся. Таким образом, в а-б достоверен только лучший результат. Это принципиальный момент и о нем не стоит забывать.

Альфа-бета у меня точно глючит. И, похоже, это не сам алгоритм а оценка. Каким образом она может глючить, я еще не понимаю. Будем разбираться.
_______________________________________________________________________________________________
Суббота, 24 мая 2008 г.
Ошибка была в оценке. Не сбрасывал в ноль статическую переменную, отвечающую за стадию игры. В результате одна и та же позиция оценивалась по-разному.
Теперь я точно знаю, что а-б без сортировки должна повторять игру полного перебора. Это очень хороший тест для а-б.
Движок играет плохо или из-за плохих алгоритмов или из-за плохой реализации этих алгоритмов. Что значит плохая реализация? Это значит медленная и с ошибками.
Дальше мне надо посмотреть, что даст второй киллер. Продумать 64 битный хеш. Продолжать работать над оценкой. Продолжать тестировать и комментировать код.
_______________________________________________________________________________________________
Суббота, 31 мая 2008 г.
Полный перебор на 6 глубине - это 119060324 позиций.
Глубина 6 за 2.06
Получается что максимальная скорость самого быстрого генератора в мире 58 миллионов позиций в секунду на Core2Duo 2690Mhz.
Этот генератор за 2 секунды дает 6 глубину, т.е. при идеальной а-б это 12 глубина. Причем надо понимать, что все эти сортировки снизят скорость и видимо довольно существенно. Думаю, где-то раз в 20 точно. А это уже 10 за 2 секунды.

У моего движка глубина 6 за 30 секунд, т.е. скорость ~ 4млн. позиций в секунду.

Таким образом, разница между лучшим генератором в мире и моим в 15 раз. Это даже полухода не даст при полном переборе!

С оценкой уже 6 за 335 сек. Т.е. замедление в 11 раз. Таким образом, генератор съедает 10% времени. Идеальный съедал бы менее 1%. Т.е. при переходе на самый быстрый в мире генератор мы бы получили ускорение в 10%.

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

Чем сложнее оценка, чем дольше она считается, тем бессмысленнее выглядит дальнейшая оптимизация генератора по скорости.
_______________________________________________________________________________________________
Четверг, 4 сентября 2008 г.
С тех пор сделал 64-битный хэш. Количество коллизий сократилось порядка на два. Но все равно остается довольно большим. В режиме только а-б + кэш при 32 битном ключе было 9813 коллизий на глубине 4, после перехода на 64 битный ключ стало 60 коллизий на глубине 5.
Так же сделал сортировку по предварительной оценке. Это для введения сортировки по истории, которую до сих пор не ввел, а вместо нее пока сортировка по централизации фигур.
Что делать дальше я пока не знаю. Значит, буду оптимизировать код и описывать структуру программы.

_______________________________________________________________________________________________