Beif9 мар 2016 в 11:08

Игра гомоку (крестики-нолики, 5 в ряд)

4 мин

84K

Алгоритмы *

+18

Комментарии 19

OlegUV 9 мар 2016 в 12:19

Статью хорошо бы дополнить теоремой о существовании/отсутствии оптимальной стратегии, вроде для 5-в-ряд что-то такое доказывали.

stasmus 9 мар 2016 в 13:04

раз

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

Joshua 9 мар 2016 в 13:29

Игра за Х доказана — форсированная победа.
Играйте за 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

stasmus 9 мар 2016 в 13:35

победа за 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

Joshua 9 мар 2016 в 13:35

Вот еще пример за 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

sozercanie_kosmosa 10 мар 2016 в 07:59

в 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

stasmus 9 мар 2016 в 13:38

еще за 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

neodavinchi 9 мар 2016 в 14:24

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 может цепочкой создать опасность в другом месте игрового поля. Таким образом, даже в гомоку один ход может повлиять практически на любую игровую клетку.

Beif 9 мар 2016 в 17:54

Да, согласен, это действительно узкое место, в конце статьи я упоминал об этой уязвимости. Здесь действительно требуется оптимизация алгоритма.

9mm 9 мар 2016 в 14:31

Хорошую вещь «гомоку» не назовут.

Greendq 9 мар 2016 в 14:37

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

Beif 9 мар 2016 в 17:56

Спасибо, хороший совет. Я тоже задумывался над уровнями сложности, но не знал как их реализовать. Ведь действительно если АИ играет очень хорошо, то большинству людей играть будет не интересно.

Joshua 9 мар 2016 в 14:48

Тут явная проблема. 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

MAXHO 9 мар 2016 в 16:19

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

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

spuf 9 мар 2016 в 17:19

Мой (достаточно простой) вариант: http://spuf.github.io/xo-game/game.html

chibiryaev 9 мар 2016 в 17:35

Предлагаю помериться у кого будет самый короткий выигрыш

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

bromozel 13 мар 2016 в 15:03

Добрый день
Я немножко умею играть в эту игру. Программа, увы, пока не особо сильная :)
Если вообще эта тема интересна, то есть даже чемпионат мира среди программ по гомоку:
http://gomocup.org
Там можно узнать о программах, которые играют сильно (непрофессионала обыграют). Если будут вопросы — пишите!

Kurtosis 1 апр 2016 в 21:39

Выигрыш в 13 ходов за X

Kurtosis 1 апр 2016 в 21:48

Аналогичная ситуация

Если запирать боту открытую двойку, то он почему-то перестает видеть очевидную вилку.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий