Pull to refresh

Comments 19

Статью хорошо бы дополнить теоремой о существовании/отсутствии оптимальной стратегии, вроде для 5-в-ряд что-то такое доказывали.
раз
New Game! X — user, O — AI AppModel.js:94:13
1: 7, 7 AppModel.js:168:9
2: 8, 6 AppModel.js:168:9
3: 7, 6 AppModel.js:168:9
4: 7, 5 AppModel.js:168:9
5: 9, 7 AppModel.js:168:9
6: 8, 7 AppModel.js:168:9
7: 8, 8 AppModel.js:168:9
8: 7, 9 AppModel.js:168:9
9: 9, 9 AppModel.js:168:9
10: 6, 6 AppModel.js:168:9
11: 9, 8 AppModel.js:168:9
12: 9, 6 AppModel.js:168:9
13: 10, 8 AppModel.js:168:9
14: 7, 8 AppModel.js:168:9
15: 10, 5 AppModel.js:168:9
16: 10, 6 AppModel.js:168:9
17: 11, 7 AppModel.js:168:9
18: 12, 6 AppModel.js:168:9
19: 11, 6 AppModel.js:168:9
20: 11, 8 AppModel.js:168:9
21: 10, 7 AppModel.js:168:9
22: 8, 9 AppModel.js:168:9
23: 12, 7 AppModel.js:168:9
24: 13, 7 AppModel.js:168:9
25: 13, 8 AppModel.js:168:9
26: 9, 4 AppModel.js:168:9
27: 14, 9 AppModel.js:168:9


два
New Game! X — user, O — AI AppModel.js:94:13
1: 7, 7 AppModel.js:168:9
2: 6, 6 AppModel.js:168:9
3: 5, 7 AppModel.js:168:9
4: 6, 7 AppModel.js:168:9
5: 6, 8 AppModel.js:168:9
6: 8, 6 AppModel.js:168:9
7: 5, 9 AppModel.js:168:9
8: 5, 6 AppModel.js:168:9
9: 7, 9 AppModel.js:168:9
10: 4, 6 AppModel.js:168:9
11: 7, 6 AppModel.js:168:9
12: 7, 8 AppModel.js:168:9
13: 8, 9 AppModel.js:168:9
14: 6, 9 AppModel.js:168:9
15: 8, 10 AppModel.js:168:9
16: 9, 11 AppModel.js:168:9
17: 8, 12 AppModel.js:168:9
18: 8, 11 AppModel.js:168:9
19: 7, 11 AppModel.js:168:9
20: 6, 10 AppModel.js:168:9
21: 6, 12 AppModel.js:168:9
22: 9, 9 AppModel.js:168:9
23: 7, 12 AppModel.js:168:9
24: 9, 12 AppModel.js:168:9
25: 7, 10 AppModel.js:168:9
26: 7, 13 AppModel.js:168:9
27: 5, 12 AppModel.js:168:9
28: 4, 12 AppModel.js:168:9
29: 6, 11 AppModel.js:168:9
30: 9, 8 AppModel.js:168:9
31: 4, 13 AppModel.js:168:9

Игра за Х доказана — форсированная победа.
Играйте за 0.

38 ходов
1: 7, 7
AppModel.js:168 2: 8, 6
AppModel.js:168 3: 7, 6
AppModel.js:168 4: 7, 5
AppModel.js:168 5: 9, 7
AppModel.js:168 6: 6, 7
AppModel.js:168 7: 8, 7
AppModel.js:168 8: 6, 6
AppModel.js:168 9: 6, 5
AppModel.js:168 10: 9, 8
AppModel.js:168 11: 5, 7
AppModel.js:168 12: 10, 7
AppModel.js:168 13: 8, 9
AppModel.js:168 14: 6, 8
AppModel.js:168 15: 8, 8
AppModel.js:168 16: 10, 6
AppModel.js:168 17: 6, 10
AppModel.js:168 18: 7, 9
AppModel.js:168 19: 8, 10
AppModel.js:168 20: 8, 11
AppModel.js:168 21: 7, 10
AppModel.js:168 22: 9, 10
AppModel.js:168 23: 10, 9
AppModel.js:168 24: 9, 6
AppModel.js:168 25: 11, 6
AppModel.js:168 26: 8, 4
AppModel.js:168 27: 8, 5
AppModel.js:168 28: 9, 3
AppModel.js:168 29: 10, 2
AppModel.js:168 30: 10, 4
AppModel.js:168 31: 10, 5
AppModel.js:168 32: 9, 4
AppModel.js:168 33: 7, 4
AppModel.js:168 34: 9, 5
AppModel.js:168 35: 9, 2
AppModel.js:168 36: 7, 3
AppModel.js:168 37: 11, 7
AppModel.js:168 38: 6, 2

победа за 0
New Game! X — AI, O — user AppModel.js:92:13
1: 7, 7 AppModel.js:168:9
2: 7, 6 AppModel.js:168:9
3: 6, 6 AppModel.js:168:9
4: 8, 8 AppModel.js:168:9
5: 5, 5 AppModel.js:168:9
6: 8, 7 AppModel.js:168:9
7: 6, 5 AppModel.js:168:9
8: 8, 9 AppModel.js:168:9
9: 8, 6 AppModel.js:168:9
10: 6, 8 AppModel.js:168:9
11: 7, 8 AppModel.js:168:9
12: 7, 9 AppModel.js:168:9
13: 8, 10 AppModel.js:168:9
14: 6, 9 AppModel.js:168:9
15: 9, 9 AppModel.js:168:9
16: 6, 10 AppModel.js:168:9
17: 9, 7 AppModel.js:168:9
18: 6, 11 AppModel.js:168:9
19: 6, 12 AppModel.js:168:9
20: 6, 7 AppModel.js:168:9

Вот еще пример за 0. Тут AI игнорирует свою победу в 3 хода, вместо этого защищается и проигрывает.

36 ходов
1: 7, 7
AppModel.js:168 2: 8, 6
AppModel.js:168 3: 7, 6
AppModel.js:168 4: 7, 8
AppModel.js:168 5: 7, 5
AppModel.js:168 6: 5, 6
AppModel.js:168 7: 6, 7
AppModel.js:168 8: 8, 7
AppModel.js:168 9: 8, 5
AppModel.js:168 10: 5, 8
AppModel.js:168 11: 5, 7
AppModel.js:168 12: 8, 8
AppModel.js:168 13: 6, 8
AppModel.js:168 14: 6, 9
AppModel.js:168 15: 9, 6
AppModel.js:168 16: 8, 9
AppModel.js:168 17: 8, 10
AppModel.js:168 18: 7, 9
AppModel.js:168 19: 5, 9
AppModel.js:168 20: 6, 10
AppModel.js:168 21: 9, 7
AppModel.js:168 22: 7, 10
AppModel.js:168 23: 4, 7
AppModel.js:168 24: 3, 7
AppModel.js:168 25: 9, 8
AppModel.js:168 26: 9, 9
AppModel.js:168 27: 10, 9
AppModel.js:168 28: 5, 11
AppModel.js:168 29: 4, 12
AppModel.js:168 30: 8, 11
AppModel.js:168 31: 9, 12
AppModel.js:168 32: 7, 11
AppModel.js:168 33: 7, 12
AppModel.js:168 34: 6, 11
AppModel.js:168 35: 4, 11
AppModel.js:168 36: 9, 11

в 25
New Game! X — user, O — AI
AppModel.js:164 1: 6, 7
AppModel.js:164 2: 7, 7
AppModel.js:164 3: 7, 6
AppModel.js:164 4: 8, 5
AppModel.js:164 5: 5, 8
AppModel.js:164 6: 4, 9
AppModel.js:164 7: 4, 7
AppModel.js:164 8: 6, 9
AppModel.js:164 9: 5, 6
AppModel.js:164 10: 5, 9
AppModel.js:164 11: 7, 9
AppModel.js:164 12: 6, 8
AppModel.js:164 13: 8, 6
AppModel.js:164 14: 6, 6
AppModel.js:164 15: 8, 8
AppModel.js:164 16: 6, 10
AppModel.js:164 17: 6, 5
AppModel.js:164 18: 7, 4
AppModel.js:164 19: 8, 7
AppModel.js:164 20: 9, 8
AppModel.js:164 21: 8, 9
AppModel.js:164 22: 8, 10
AppModel.js:164 23: 7, 8
AppModel.js:164 24: 9, 10
AppModel.js:164 25: 4, 5

еще за 0
New Game! X — AI, O — user AppModel.js:92:13
1: 7, 7 AppModel.js:168:9
2: 6, 7 AppModel.js:168:9
3: 7, 6 AppModel.js:168:9
4: 7, 8 AppModel.js:168:9
5: 5, 6 AppModel.js:168:9
6: 6, 6 AppModel.js:168:9
7: 6, 8 AppModel.js:168:9
8: 8, 6 AppModel.js:168:9
9: 6, 5 AppModel.js:168:9
10: 7, 5 AppModel.js:168:9
11: 5, 7 AppModel.js:168:9
12: 9, 7 AppModel.js:168:9
13: 6, 4 AppModel.js:168:9
14: 8, 7 AppModel.js:168:9
15: 8, 8 AppModel.js:168:9
16: 9, 6 AppModel.js:168:9
17: 6, 9 AppModel.js:168:9
18: 10, 5 AppModel.js:168:9
19: 11, 4 AppModel.js:168:9
20: 10, 8 AppModel.js:168:9
21: 11, 9 AppModel.js:168:9
22: 10, 7 AppModel.js:168:9
23: 10, 6 AppModel.js:168:9
24: 8, 5 AppModel.js:168:9
25: 7, 4 AppModel.js:168:9
26: 9, 5 AppModel.js:168:9
27: 11, 5 AppModel.js:168:9
28: 9, 4 AppModel.js:168:9
29: 9, 3 AppModel.js:168:9
30: 9, 8 AppModel.js:168:9

38, выиграл за 0
X — AI, O — user
1: 7, 7
2: 6, 7
3: 7, 6
4: 7, 8
5: 5, 6
6: 6, 6
7: 6, 8
8: 8, 6
9: 7, 5
10: 7, 3
11: 6, 5
12: 4, 7
13: 8, 7
14: 5, 4
15: 5, 5
16: 4, 5
17: 4, 6
18: 6, 3
19: 3, 6
20: 7, 2
21: 8, 1
22: 7, 4
23: 8, 5
24: 9, 5
25: 5, 7
26: 3, 5
27: 8, 4
28: 7, 1
29: 7, 0
30: 8, 3
31: 9, 3
32: 5, 3
33: 4, 3
34: 6, 1
35: 6, 2
36: 9, 4
37: 10, 5
38: 5, 0


Думаю, что узкое место AI находится вот тут:

Я предположил, что… ходы локальны (имеют относительно малый радиус влияния в отличии от шахмат, например)

По моему опыту, выигрыш часто получается чередой опасных моментов для противника, а поставленный в нужном месте 0 может цепочкой создать опасность в другом месте игрового поля. Таким образом, даже в гомоку один ход может повлиять практически на любую игровую клетку.
Да, согласен, это действительно узкое место, в конце статьи я упоминал об этой уязвимости. Здесь действительно требуется оптимизация алгоритма.
Хорошую вещь «гомоку» не назовут.
Я реализовывал когда-то "5 в ряд" для Киндла (который читалка) (и "6 в ряд" на её основе потом). За основу был взят классический вариант реплизации min-max из примеров для Борландовской реализации Паскаля.
QA Амазона выкатили единственную претензию — "игра слишком сложна и не прощает ошибок. Добавьте уровни сложности". Пришлось вводить "случайные" ошибки — т.е. ИИ тупо делал ошибки в зависимости от уровня сложности.
Спасибо, хороший совет. Я тоже задумывался над уровнями сложности, но не знал как их реализовать. Ведь действительно если АИ играет очень хорошо, то большинству людей играть будет не интересно.
Тут явная проблема. AI не увидел угрозы в полуоткрытой 4-ке.

22 хода
New Game! X — AI, O — user
AppModel.js:168 1: 7, 7
AppModel.js:168 2: 8, 6
AppModel.js:168 3: 7, 6
AppModel.js:168 4: 9, 5
AppModel.js:168 5: 7, 5
AppModel.js:168 6: 7, 8
AppModel.js:168 7: 7, 4
AppModel.js:168 8: 7, 3
AppModel.js:168 9: 8, 4
AppModel.js:168 10: 10, 4
AppModel.js:168 11: 6, 6
AppModel.js:168 12: 9, 3
AppModel.js:168 13: 9, 4
AppModel.js:168 14: 8, 2
AppModel.js:168 15: 11, 5
AppModel.js:168 16: 6, 4
AppModel.js:168 17: 5, 5
AppModel.js:168 18: 4, 4
AppModel.js:168 19: 8, 5
AppModel.js:168 20: 11, 3
AppModel.js:168 21: 10, 3
AppModel.js:168 22: 12, 2

проблема даже не в том что выигрываю,
Проблема что компьютер играет "скушно".

Кстати, это интересная игровая проблема — как написать ИИ играющий "интересно". Т.е. ходы которого не просто набор оптимальных на глубину поиска, а "атакующие" или "защищающиеся" или "коварные". Именно субъективность делает игру интересной.
Предлагаю помериться у кого будет самый короткий выигрыш

17 ходов
New Game! X — user, O — AI
AppModel.js:168 1: 7, 7
AppModel.js:168 2: 8, 7
AppModel.js:168 3: 7, 4
AppModel.js:168 4: 7, 6
AppModel.js:168 5: 6, 5
AppModel.js:168 6: 5, 6
AppModel.js:168 7: 6, 4
AppModel.js:168 8: 6, 6
AppModel.js:168 9: 8, 6
AppModel.js:168 10: 7, 5
AppModel.js:168 11: 8, 4
AppModel.js:168 12: 5, 4
AppModel.js:168 13: 10, 4
AppModel.js:168 14: 9, 4
AppModel.js:168 15: 9, 5
AppModel.js:168 16: 6, 8
AppModel.js:168 17: 11, 3

Добрый день
Я немножко умею играть в эту игру. Программа, увы, пока не особо сильная :)
Если вообще эта тема интересна, то есть даже чемпионат мира среди программ по гомоку:
http://gomocup.org
Там можно узнать о программах, которые играют сильно (непрофессионала обыграют). Если будут вопросы — пишите!
Аналогичная ситуация
image
Если запирать боту открытую двойку, то он почему-то перестает видеть очевидную вилку.
Only those users with full accounts are able to leave comments. Log in, please.