Здравствуйте, Уважаемые Кодеры.
Написал недавно на qBasic крестики-нолики 3x3 на два игрока. Решил сделать возможность играть с компьютером. Какой алгоритм лучше всего использовать?
Огромное спасибо
Здравствуйте, Уважаемые Кодеры.
Написал недавно на qBasic крестики-нолики 3x3 на два игрока. Решил сделать возможность играть с компьютером. Какой алгоритм лучше всего использовать?
Огромное спасибо
Когда то я делал такую логику для программируемого калькулятора. Там памяти мало будет (105 шагов, один шаг это присваивание, умножение, if), так что сильно не разбежаться.
Вначале оценим, сколько возможно вариантов вообще. Логика подсказывает, что первый может походить 9 вариантами, второй 8 и так далее, что дает 9! = 362880. Но чуточку поразмыслив, понятно, что при первом ходе возможно 3 варианта, все остальное - зеркально. Да и не все варианты со стороны компьютера нам нужны (зачем нам хранить проигрышные варианты?). Поэтому, если начинает человек, то у него 3 варианта, у компа - 1 (мы заведомо знаем, куда пойдем), дальше у пользователя 7 вариантов и пять. 375 = 105 вариантов - это уже очень немного. У меня получалось всего около 200-250 возможных вариантов.
То есть, всю логику можно впихнуть в граф ходов. Первым делом занумеруем правильно поле
1 2 3
8 0 4
7 6 5
При таком подходе очень легко обрабатывать зеркальные варианты. То есть, если пользователь походил первый и начал с клетки 5, то мы просто мысленно разворачиваем поле и считаем, что он походил с клетки 1. Первый ход пользователя может быть только с клеток 0 1 или 2. Компьютеру можно начинать игру всегда с одной и той же клетки (если правильно помню свои выкладки, то начиная с центральной клетки и делать правильные хода, то можно либо выиграть, либо свести к ничье).
Теперь осталось сделать граф ходов. Это делается на листике бумаги либо просчитывается программно.
Сами раскладки предлагаю хранить в виде 9 символьных строк + номер клетки для хода.
OO.XX.... ->4
OXOOXX... ->6
OO.XX.... это просто построчная запись
O O .
X X .
. . .
А можно использовать граф. Узлами будут номера клеток противника + номер ответа. буквой w я обозначил конец игры. * - где мне лень писать далее. Вариант 0 - 2 - я расписал полностью и как видно он выигрышный при любых последующих ходах. (C - computer - компьютер, U - User - пользователь).
C U C U C U C
0 - 1 - 2 - 3 - 6,w
- 4 - 6,w
- 5 - 6,w
- 6 - 7 - *
- 7 - 6,w
- 8 - 6,w
- 2 - 1 - 3 - 5,w
- 4 - 5,w
- 7 - 5,w
- 6 - 5,w
- 8 - 5,w
- 5 - 8 - 3 - 7,w
- 4 - 7,w
- 6 - 7,w
- 7 - 4,w
Этот алгоритм очень легко кодируется.
Для того, что бы хода компьютера не выглядели одинаково, в тех случаях, когда возможны различные хода, можно рандомом выбирать.
Алгоритмов не так уж много для поля 3*3
Описывать любой времени много уйдет, самое простое возьми любую программу готовую и поиграй партий 100-200 поймешь как и куда ходить. А потом уже реализуй ветвления.
ИИ для поля 3х3 звучит как-то слишком сильно. Он имеет смысл для полей, скажем, 50х50.
А для небольших полей, самое очевидное решение -- полный перебор(для мелких), либо частичный перебор уже в процессе игры. Шахматные движки при анализе используют частичный перебор и эвристику.
Т.е. просто строите полное дерево позиций(оно будет небольшим), приводите к двум оптимальным деревьям поменьше: за крестиков и за ноликов. И всё, ИИ готов :)
Все сведется к тому что будет бесконечно ничья ( если идеально играть ), подумайте над процентами вероятности, т.е. один раз компьютер может сделать верный ход, а когда-нибудь в другой раз при низком коеф. вероятности компьютер сделает неверный ход. Я как-то даже делал уровни сложности: легко, средне, тяжело.