Форум программистов, компьютерный форум CyberForum.ru

Интеллект компьютера в игре Крестик-Нолик - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
^Tecktonik_KiLLeR
 Аватар для ^Tecktonik_KiLLeR
1144 / 426 / 19
Регистрация: 23.06.2009
Сообщений: 6,141
Завершенные тесты: 1
01.04.2014, 22:47     Интеллект компьютера в игре Крестик-Нолик #1
вот написал себе игру крестик нолик. Все нормально получилось. Просто вот не могу объяснить компьютеру как правильно думать.
У меня есть схема тактики в игре.
Вот:Интеллект компьютера в игре Крестик-Нолик
А вот и сам код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
#include "stdafx.h"
#include <iostream>
#include <Windows.h>
#include <time.h>
using namespace std;
 
void out(int board[][3], int);  //Matrix print
int CFW(int board[][3], int);   //Check For Win
void CT(int board[][3], int,char,bool); //Computer turn
void UT(int board[][3], int);   //User turn
int main()
{
    srand(time(NULL));
    char turn;  //Начальный спрос, игра юзера или компьюера
    bool first=true;    
    const int a=3;  //размер матрицы
    int board[a][a];    //сама матрица
    for(int i=0;i<a;i++)
        for(int j=0;j<a;j++)
            board[i][j]=0;  // обнуление служит для пустой доски. 0-пустой квадрат, 1-крестик юзера, 2-ноль компьютера
    out(board,a);
    trn: cout<<"Your first turn? y/n: ";    //кто первым начнет
    cin>>turn;
    if(turn=='y' || turn=='n');
    else
    {
        cout<<"Illegal symbol."<<endl;
        goto trn;
    }
    system("cls");
    //Game Start
    while(true)
    {
        cout<<"KRESTIK NOLIK"<<endl;    
        if(CFW(board,a))    //Проверка на случай ничьи
            break;      // конец цикла
        if(turn=='y')
        {
        //ход игрока
        out(board,a);
        UT(board,a);
        //ход компьютера
        CT(board,a,turn,first);
        }
        else
        {
        //comp turn
        CT(board,a,turn,first); 
        out(board,a);
        //user turn
        UT(board,a);            
        }       
        system("cls");
        first=false;    //после этого уже не первый ход
    }
    out(board,a);
    if(CFW(board,a)==1)
        cout<<endl<<"YOU WIN!!!"<<endl;
    else if(CFW(board,a)==2)
        cout<<endl<<"YOU LOSE!!!"<<endl;
    else
        cout<<endl<<"DRAW"<<endl;
    system("pause");
    return 0;
}
 
void out(int board[][3], int a)
{
    for(int i=0;i<a;i++)
    {
        for(int j=0;j<a;j++)
        {
            if(board[i][j]==0)
            cout<<"| ";
            else if(board[i][j]==1)
                cout<<"|X";
            else if(board[i][j]==2)
                cout<<"|0";
        }
        cout<<"|"<<endl;
    }
}
int CFW(int board[][3], int a)
{
    for(int i=0;i<a;i++)
    {
        if(board[i][0]==board[i][1]
        && board[i][1]==board[i][2]
        && board[i][2]==1) // user win 
            return 1;       
    }
 
    for(int i=0;i<a;i++)
    {
        if(board[0][i]==board[1][i]
        && board[1][i]==board[2][i]
        && board[2][i]==1) // user win 
            return 1;       
    }
 
    if(board[0][0]==board[1][1]
    && board[1][1]==board[2][2]
    && board[2][2]==1)  //user win
        return 1;
    if(board[0][2]==board[1][1]
    && board[1][1]==board[2][0]
    && board[1][1]==1)  //user win
        return 1;
 
 
    ////////////////////////
 
 
    for(int i=0;i<a;i++)
    {
        if(board[i][0]==board[i][1]
        && board[i][1]==board[i][2]
        && board[i][2]==2) // comp win 
            return 2;       
    }
 
    for(int i=0;i<a;i++)
    {
        if(board[0][i]==board[1][i]
        && board[1][i]==board[2][i]
        && board[2][i]==2) // comp win 
            return 2;       
    }
 
    if(board[0][0]==board[1][1]
    && board[1][1]==board[2][2]
    && board[2][2]==2)  //comp win
        return 2;
    if(board[0][2]==board[1][1]
    && board[1][1]==board[2][0]
    && board[1][1]==2)  //comp win
        return 2;
 
    return 0;   //draw
}
void UT(int board[][3], int a)
{
    int x,y;
    loop: cin>>x>>y;
        x--;y--;        //пользователь не будет вводит координаты типа 0.0, а 1.1
        if(board[x][y]==0)
        board[x][y]=1;
        else
        {
            cout<<"again!"<<endl;
            goto loop;
        }
}
void CT(int board[][3],int a,char turn,bool first)
{
    //first turn
    int r;
    int c;  
    if(turn=='n' && first==true)
    {
        r=rand()%5;
        if(r==0)
            board[0][0]=2;
        else if(r==1)
            board[0][2]=2;
        else if(r==2)
            board[2][0]=2;
        else if(r==3)
            board[2][2]==2;
        else if(r==4)
            board[1][1]==2;
        return;
    }
 
 
    //вот здесь уже компьютер играет "рандом"-не думает
    random: r=rand()%3;
            c=rand()%3;
    if(board[r][c]!=0)
        goto random;
    else
        board[r][c]=2;
 
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.04.2014, 22:47     Интеллект компьютера в игре Крестик-Нолик
Посмотрите здесь:

C++ крестик-нолик - функция победы
C++ крестик-нолик-условие ничьи
крестик-нолик - функция пoбеды C++
Алгоритм ходов компьютера в карточной игре "Дурак" C++
искусственный интеллект C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
НеСказочник
58 / 46 / 7
Регистрация: 12.11.2012
Сообщений: 339
Записей в блоге: 2
02.04.2014, 08:55     Интеллект компьютера в игре Крестик-Нолик #2
Так и в чём проблема? Если
Цитата Сообщение от ^Tecktonik_KiLLeR Посмотреть сообщение
есть схема тактики в игре
Создайте список или словарь, где ключём будет текущее состояние поля, а данными координаты хода. И выбирайте поиском. Для игры "Крестики нолики" словарь будет не такой уж и большой.

Добавлено через 4 минуты
19683 - вариантов. словарь, отсилы, полмегабайта будет, а то и меньше. А если хранить данные одной ячейки в char, то вообще 171 КБ. Компьютер будет не больше 50 мкс думать.

Добавлено через 53 секунды
Но это если клеточек 9 . 3X3.

Добавлено через 2 минуты
Вот если бы вариантов было как в шахматах, порядка 10^50, то пришлось бы обучать случайный лес или что-то подобное. А для "Крестики нолики", даже не заморачивайтесь.
^Tecktonik_KiLLeR
 Аватар для ^Tecktonik_KiLLeR
1144 / 426 / 19
Регистрация: 23.06.2009
Сообщений: 6,141
Завершенные тесты: 1
02.04.2014, 10:54  [ТС]     Интеллект компьютера в игре Крестик-Нолик #3
НеСказочник, ну дело в том что я не понимаю ни список не ключи. Можете мне пример написать кода?
НеСказочник
58 / 46 / 7
Регистрация: 12.11.2012
Сообщений: 339
Записей в блоге: 2
02.04.2014, 11:32     Интеллект компьютера в игре Крестик-Нолик #4
Если компьютер всегда играет нулями, то всё просто.
Я это как-то так вижу:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <map>
 
using namespace std;
 
struct XOmap //Карта поля, я взял структуру, так как с ней проще, можно методы внутрь запихнуть.
{
 char a[3][3];
 
 bool step(XOstep nstep,char symbol)
 {
  if ((nstep.r < 3) && (nstep.c < 3))
  {
   a[nstep.r][nstep.c] = symbol;
   return true;
  }
  else
   return false; //Возвращает false, если ход вне поля (так просто защита от дурака)
 }
}
 
struct XOstep //структура для хранения одного хода компьютера
{
 unsigned char r,c;  //строка, столбец, где нужно поставить нолик.
}
 
map<XOmap,XOstep> AI_DataBase;
 
XOmap CurrentMap; //карта игрового поля
 
//......   тут остальной ваш код
//...... И после каждого хода игрока компьютер ходит так
XOstep nextStep=AI_DataBase[CurrentMap];   //Выбираем из базы наилучший ход для текущей ситуации
CurrentMap.step(nextStep,2);                 //И ходим
//....... И дальше прочий код.
Добавлено через 4 минуты
Только вот AI_DataBase заполнять будете сами. Туда, собственно, и запихивается стратегия игры.

Добавлено через 2 минуты
Можно попытаться читать из файла, или написать метод, заполняющий map при запуске. Вот справка по map и ещё на русском.

Добавлено через 1 минуту
Только не пытайтесь использовать данный метод для чего-то сложнее, чем крестики нолики. Так обычно не делают, но задача слишком уж простая, что бы настоящий AI подключать.
^Tecktonik_KiLLeR
 Аватар для ^Tecktonik_KiLLeR
1144 / 426 / 19
Регистрация: 23.06.2009
Сообщений: 6,141
Завершенные тесты: 1
02.04.2014, 12:50  [ТС]     Интеллект компьютера в игре Крестик-Нолик #5
Цитата Сообщение от НеСказочник Посмотреть сообщение
Только вот AI_DataBase заполнять будете сами.
Спасибо большое конечно за код, но я открыл пост для того чтобы помогли создать стратегию. Сам то могу, но будет ооочень много усл. операторов if ..else
Думаю чтобы сократить кол-во усл. операторов, можно использовать циклы, но как?
НеСказочник
58 / 46 / 7
Регистрация: 12.11.2012
Сообщений: 339
Записей в блоге: 2
02.04.2014, 13:08     Интеллект компьютера в игре Крестик-Нолик #6
Цитата Сообщение от ^Tecktonik_KiLLeR Посмотреть сообщение
будет ооочень много усл. операторов if ..else
Думаю чтобы сократить кол-во усл. операторов, можно использовать циклы, но как?
Какие циклы? Какие условные операторы? Вам нужно просто заполнить AI_DataBase. Можно на крайний случай запустить кучу игр со случайными ходами, в конце каждой из которых программа будет прибавлять веса ходам победителя и убавлять ходам проигравшего.
Т.е. тут у вас получится что-то вроде:
C++
1
map<XOmap,map<XOstep, int>> AllSteps;
Т.е. каждому состоянию поля соответствует map, в котором ключи - это ходы, а значения - их веса. Компьютер обучается Только один раз за всю жизнь. Играет случайно сам с собой до победы, потом Вы берёте каждый ход победителя (в связке с текущим состоянием поля, конечно) и увеличиваете его вес на 1, а у ходов проигравшего все веса уменьшить на 1. Прокрутить несколько миллионов игр для современного компа не вопрос. Потом из каждой карты map<XOstep, int> Вы выбираете тот XOstep, чей вес максимален и ставите его значением для соответствующей XOmap в map<XOmap,XOstep> AI_DataBase;. После чего AI_DataBase пишется в файл, любым удобным для вас образом, и это и будет ваша база знаний.

Добавлено через 4 минуты
Если хотите совсем заморочиться, то можно сохранить и map<XOmap,map<XOstep, int>> AllSteps; и после каждой игры плюсовать ходы, если выиграл или минусовать, если проиграл. И ваш компьютер будет в добавок самообучаем. Только тогда придётся периодически пересматривать AI_DataBase.


PS: Я как-то давноым давно пытался так шашки написать. Работало неимоверно долго, но играло неплохо. Но в шашках куда больше вариантов, а вот для крестиков и ноликов думаю как раз подойдёт.

Добавлено через 3 минуты
Это просто попытка запомнить все ходы влоб. Только вместо точного алгоритма поиска используется эвристический. Но можно и точный, т.е. просто перебрать все возможные партии, хотя это, мне кажется, даже для "Крестики нолики" будет слишком.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.04.2014, 19:56     Интеллект компьютера в игре Крестик-Нолик
Еще ссылки по теме:

C++ Список, выводит лишний нолик
C++ Искусственный интеллект
C++ Игра крестики-нолик

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
^Tecktonik_KiLLeR
 Аватар для ^Tecktonik_KiLLeR
1144 / 426 / 19
Регистрация: 23.06.2009
Сообщений: 6,141
Завершенные тесты: 1
02.04.2014, 19:56  [ТС]     Интеллект компьютера в игре Крестик-Нолик #7
НеСказочник, я с картами и ключами не знаком. Поэтому и говорю помогите мне с кодом.
Yandex
Объявления
02.04.2014, 19:56     Интеллект компьютера в игре Крестик-Нолик
Ответ Создать тему
Опции темы

Текущее время: 23:54. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru