алгаритм игры крестики - нолики

[petroff]

Люди дайте пожалуйста.... алгаритм к игре .....или исходник...
....только было б не плохо если б все было хорошо прокоментирована.
Крестики - нолики обычные.3х3

[artyuha]

Могу поделится своим, но это мой первый проект - там полная лабуда . Я его ни кому и не показывал . Да и алгоритм не совершенен.

[Inferno]

2 булевых массива, один для крестиков, другой для ноликов. Поставил нолик занес еденичку в соостветсвующую ячейку массива ноликов и посчитал не пересекается ли у тебя чегось из ноликов Для крестиков тоже самое

[artyuha]

Мне кажется, что человеку нужен интеллектуальный противник в виде компа. В моей программе это есть, хоть не сильно и интеллектуальный (в этом-то и проблемы с алгоритмом ). Хотя есть возможность игры и с живым оппонентом (но не по сети).

[Faust]

Ща зарандомлю код....

Предполагается, что есть массив A(0 to 2,0 to 2), отвечающий игровому полю. Значения A(i,j) означают следущее: 0-свободная клетка, 1-крестик, 2-нолик. Предполагается, что компьютер играет ноликами.

Код: Выделить всё


'--------------------------------------------------
'наибольший приоритет у создания собственной линии:
'--------------------------------------------------
'горизонтали и вертикали:
For i=0 to 2
For j=0 to 2
   If A(i,j)=0 then
      If A(i, (j+1) mod 3)=2 then
         If A(i,(j+2) mod 3)=2 then
            A(i,j)=2
            Exit Sub
         end if
      end if
      If A((i+1) mod 3, j)=2 then
         If A((i+2) mod 3,j)=2 then
            A(i,j)=2
            Exit Sub
         end if
      end if
   end if
Next j
Next i
'диагонали:
For i=0 to 2
If A(i,i)=0 then
   If A((i+1) mod 3,(i+1) mod 3)=2 then
      If A((i+2) mod 3,(i+2) mod 3)=2 then
         A(i,j)=2
         Exit Sub
      end if
   end if
end if
If A(i,2-i)=0 then
   If A((i+1) mod 3,2-(i+1) mod 3)=2 then
      If A((i+1) mod 3,2-(i+2) mod 3)=2 then
         A(i,j)=2
         Exit Sub
      end if
   end if
end if
next i
'---------------------------------------------------
'следущий приоритет у перекрытия линии пользователя:
'---------------------------------------------------
'горизонтали и вертикали:
For i=0 to 2
For j=0 to 2
   If A(i,j)=0 then
      If A(i, (j+1) mod 3)=1 then
         If A(i,(j+2) mod 3)=1 then
            A(i,j)=2
            Exit Sub
         end if
      end if
      If A((i+1) mod 3, j)=1 then
         If A((i+2) mod 3,j)=1 then
            A(i,j)=2
            Exit Sub
         end if
      end if
   end if
Next j
Next i
'диагонали:
For i=0 to 2
If A(i,i)=0 then
   If A((i+1) mod 3,(i+1) mod 3)=1 then
      If A((i+2) mod 3,(i+2) mod 3)=1 then
         A(i,j)=2
         Exit Sub
      end if
   end if
end if
If A(i,2-i)=0 then
   If A((i+1) mod 3,2-(i+1) mod 3)=1 then
      If A((i+1) mod 3,2-(i+2) mod 3)=1 then
         A(i,j)=2
         Exit Sub
      end if
   end if
end if
next i
'------------------------
'далее идет захват центра
'------------------------
If a(1,1)=0 then
   a(1,1)=2
   exit sub
end if
'-----------------------
'далее идет захват углов
'-----------------------
For i=0 to 3
If a(2*(i \ 2),2*(i mod 2))=0 then
   a(2*(i \ 2),2*(i mod 2))=2
   exit sub
end if
next i
'-----------------------------
'наименее ценны боковые клетки
'-----------------------------
For i=0 to 3
If a((i*2+1) \ 3,(i*2+1) mod 3)=0 then
   a((i*2+1) \ 3,(i*2+1) mod 3)=2
   exit sub
end if
next i

Вот, собственно, и весь "AI".

[artyuha]

Всё теоритечески правильно, но если сходу захватывать центральную клетку, то далее игра лишена всякого смысла и переходит в монотонное перекрытие незаконченных линий противника. В моём же боте существует не гласное правило не занемать центральную клетку и тогда появляется несколько интересных моментов развития игры. Вообще игра очень проста и даже используя это правило всё сводится к тому, что в зависимости от ситуации на поле можно провести комбинацию которая приводит к 100% выигршу или "ни чей". Так ка поле не большое 3x3 таких комбинаций не много.

[GSerg]

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

[Опришник]

Код: Выделить всё

Option Explicit

' P - игровое поле
' Player - ходящий игрок (1-крестик, 2-нолик)
' При начале игры Player=1
Public P(1 To 3, 1 To 3) As Byte, Player As Byte

Public Type TPOINT
    X As Byte
    Y As Byte
End Type

' Возвращает кол-во подряд идущих элементов равных M
' Начинает отчёт с (X,Y) с шагом (StepX,StepY)
' Если цепочка обрываеться не нулём, возвращает 0
Private Function GetLineFg(ByVal X As Byte, ByVal Y As Byte, M As Byte, StepX%, StepY%) As Byte
    X = X + StepX
    Y = Y + StepY
    Do While X >= 1 And Y >= 1 And X <= 3 And Y <= 3
        If P(X, Y) <> M Then GoTo 1
        GetLineFg = GetLineFg + 1
        X = X + StepX
        Y = Y + StepY
    Loop
    Exit Function
1:  If P(X, Y) Then GetLineFg = 0
End Function

' Возвращает оценку хода
Private Function StepPr(X As Byte, Y As Byte) As Byte
    Dim lFg As Byte
    Dim pI As Byte, J As Byte
    For pI = 1 To 2
        For J = 0 To 2
            lFg = GetLineFg(X, Y, pI, J - 1, -1) + _
                  GetLineFg(X, Y, pI, 1 - J, 1)
            StepPr = StepPr + lFg ^ (2 - (pI = Player))
        Next
        lFg = GetLineFg(X, Y, pI, 1, 0) + _
              GetLineFg(X, Y, pI, -1, 0)
        StepPr = StepPr + lFg ^ (2 - (pI = Player))
    Next
End Function

' если X=0, то функция находит точку
'      с максимальной оценкой, делает ход, возвращает координаты
' иначе просто делает ход в указанную точку
Public Function Step(Optional ByVal X As Byte = 0, Optional ByVal Y As Byte = 0) As TPOINT
    If X = 0 Then
        Dim I As Byte, J As Byte
        Dim MPr As Byte, TPr As Byte
        If P(2, 2) = 0 Then
            X = 2
            Y = 2
            MPr = StepPr(2, 2)
        End If
        For J = 1 To 3
            For I = 1 To 3
                If P(I, J) = 0 Then
                    TPr = StepPr(I, J)
                    If TPr > MPr Then
                        MPr = TPr
                        X = I
                        Y = J
                    End If
                End If
            Next
        Next
        Step.X = X
        Step.Y = Y
    End If
    P(X, Y) = Player
    Player = 3 - Player
End Function

Важный момент:
при идеальной игре обоих игроков теоретически на поле 3x3 не будет победителя!!! (доказуется практикой(или полным перебором!!!))

[|kerish|]

Опришник Апплодирую!

[petroff]

Отлично ...Большое спасибо .......

Помоему два этих примера отличаются реализацией ?? в первом методом перебора ....а во втором вычеслением отрезка ??
....если можно поподробней насчет второго....

....а то написал графический инетрефейс ..взялся за ai ....и тут попал в ступор ...... получился громадный участок кода ....который то работал то нет ......

[artyuha]

Допустим пользователь играет крестиками и ходит первым. Вот комбинация которая даёт 100% выиграш в при первом алгоритме и (насколько я разобрался) втором

[petroff]

Второй алгоритм круче .... Но непонятный .... зато можно заставить играть на большом поле ....
Так не кто не распишет второй алгоритм ??

[petroff]

to Faust
Классно предумал с моД .... не когда б не додумался
Честно говоря алгоритм слишком прямой ....всегда будет делать одно тоже и первыми будет занимтаь клетки которые запргаграмированы....

первый алгоритм не подойдет если поле больше 3 клеток


If P(X, Y) Then GetLineFg = 0

Что означает сие ??? если P(X, Y) равняется чему ??
StepX%, StepY% что за переменые ??

[Faust]

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

[petroff]

to Faust
НЕт ето не задача по информатике ето для себя , хочется чтоб комп прошитивал ходы как человек .....вот с етим и сложности ......не могу разобратся со вторым алгоритмом !!!