Costas-Tyros_rus_MS

getWgt_nd:(unsigned, real) nondeterm (o, o). assertWgt:(unsigned I, real W) procedure (i, i). popweight:(unsigned I, real W) procedure (i, i). usit:( real*, real) procedure ( i, o). setExamples:(examples) procedure (i). getWgt:(unsigned, real) procedure (i, o). hidden:(unsigned, unsigned*, real) procedure (i, i, o). setEx:(unsigned, examples).

end interface network

Добавьте нижеприведённый листинг к network.pro. Постройте приложение.

%File network.pro implement network open core constants

className = "network/network". classVersion = "".

facts

weight:(unsigned, real). eg:(unsigned, real, real, real).

clauses

sigmoid(X)= 1.0/(1.0+math::exp( X)). getWgt_nd(I, R) : weight(I, R). assertWgt(I, R) : asserta(weight(I, R)). popweight(I, W) : retract(weight(I, W)), !. popweight(_, _).

setExamples(Es) : retractall(eg(_,_,_,_)), setEx(0, Es).

setEx(_N, []) : !.

setEx(N, [e(I1, I2,R)|Es]) : assertz(eg(N, I1, I2, R)), setEx(N+1, Es).

egratia(Eg, I1, I2, Output) : eg(Eg, I1, I2, Output), !. egratia(Eg, I1, I2, Output) : Ex = Eg rem 4,

eg(Ex, I1, I2, Output), !. egratia(_Eg, 1, 1, 0). setWeight(Qs) :

retractall(weight(_,_)),

foreach tuple(X, WX)= list::getMember_nd(Qs) do assert(weight(X, WX))

end foreach.

getWgt(I, W) : weight(I, W), !. getWgt(_I, 0.0). predicted_out(Obj, V) :

hidden(Obj, [3,4,5], I_1), hidden(Obj, [6,7,8], I_2), getWgt(0, W_0),

getWgt(1, W_1), getWgt(2, W_2),

X = W_0+W_1* I_1 + W_2* I_2, V= sigmoid(X).

hidden(Obj,[A,B,C],V) : eg(Obj, I_1, I_2, _), !, getWgt(A, WA),

161

getWgt(B, WB), getWgt(C, WC),

XX = WA+WB* I_1+WC* I_2, V=sigmoid(XX).

hidden(_, _, 0). usit( [I1, I2], V) :

getWgt(0, W_0), getWgt(1, W_1), getWgt(2, W_2), getWgt(3, W_3), getWgt(4, W_4), getWgt(5, W_5), getWgt(6, W_6), getWgt(7, W_7), getWgt(8, W_8), !, X1 = W_3 + W_4*I1 + W_5*I2,

V1=sigmoid(X1),

X2 = W_6 + W_7*I1 + W_8*I2, V2= sigmoid(X2),

VX = W_0 + W_1*V1 + W_2*V2, V= sigmoid(VX).

usit( _, 0).

end implement network

Объекты класса network могут играть роль нейрона. В главном модуле вы найдёте обучающую

программу, а также тестовый предикат run() для логических вентилей «И» и «исключающее ИЛИ». Постройте приложение, и запустите в окне – Run in Window.

% Файл main.pro implement main open core constants

className = "main". classVersion = "nnxor".

clauses

classInfo(className, classVersion). class facts

acc:real := 0.0. nn:network := erroneous.

class predicates

evalError:(unsigned Obj, real Err) procedure (i, o).

errSum:(unsigned* Exs, real Partial_err, real Total_err) procedure (i, i, o). updateWeight:(real DX, real LC, unsigned* Exs) procedure (i, i, i).

clauses

evalError(Obj, E) : nn:predicted_out(Obj, VC), nn:egratia(Obj, _I1, _I2, V),

E= (VC V)*(VC V).

errSum(Exs, _Partial_err, Total_err) : acc := 0.0, foreach Eg= list::getMember_nd(Exs) do

evalError(Eg, Err), acc := acc + Err

end foreach, Total_err= acc.

updateWeight(DX, LC, Exs) : errSum(Exs, 0.0, Err0), PN= [tuple(I, W) || nn:getWgt_nd(I, W)],

nn:setWeight([tuple(P, NV) || tuple(P, V)= list::getMember_nd(PN), V1= V+DX,

nn:assertWgt(P, V1), errSum(Exs, 0.0, Nerr), nn:popweight(P, V1),

162

NV= V+LC*(Err0 Nerr)/DX]).

class predicates

train:(real DX, real LC, unsigned* Exs) procedure (i, i, i). clauses

train(DX, LC, Exs) : errSum(Exs, 0, Err0), if (Err0 < 0.1) then

stdio::write("Total Err: ", Err0), stdio::nl

else

updateWeight(DX, LC, Exs), train(DX, LC, Exs)

end if. class predicates

training:(network, real, real) procedure (i, i, i). clauses

training(NN, _DX, _LC) : nn := NN,

WWW= [tuple(0,0),tuple(1,2),tuple(2,0), tuple(3,0),tuple(4,1),tuple(5,0), tuple(6,0),tuple(7,0),tuple(8,0)],

nn:setWeight(WWW),

train(0.001,0.1,[0,1,2,3, 1, 2, 3, 0, 3, 2, 1, 0]). run(): console::init(),

XOR = network::new(), AND = network::new(), XOR:setExamples([ network::e(1,1,0), network::e(1,0,1),

network::e(0,1,1), network::e(0,0,0)]), AND:setExamples([ network::e(1,1,1), network::e(1,0,0), network::e(0,1,0), network::e(0,0,0)]),

training(XOR, 0.001, 0.5), training(AND, 0.001, 0.5), XOR:usit( [1,1], XOR11), stdio::nl,

stdio::write("xor(1,1)=", XOR11), stdio::nl, XOR:usit( [1,0], XOR10), stdio::nl, stdio::write("xor(1,0)=", XOR10), stdio::nl, XOR:usit( [0,1], XOR01), stdio::nl, stdio::write("xor(0,1)=", XOR01), stdio::nl, XOR:usit( [0,0], XOR00), stdio::nl,

stdio::write("xor(0,0)=", XOR00), stdio::nl, stdio::nl, AND:usit( [1,1], AND11), stdio::nl, stdio::write("1&&1=", AND11), stdio::nl,

AND:usit( [1,0], AND10), stdio::nl, stdio::write("1&&0=", AND10), stdio::nl, AND:usit( [0,1], AND01), stdio::nl, stdio::write("0&&1=", AND01), stdio::nl, AND:usit( [0,0], AND00), stdio::nl, stdio::write("0&&0=", AND00), stdio::nl.

end implement main goal

mainExe::run(main::run).

24.3.Запуск двуслойной нейросети

После компоновки приложения neurons, запустив его, вы получите следующий результат:

Total Err: 0.09983168220091619

Total Err: 0.09968265082000113

163

xor(1,1)=0.08040475166406771

xor(1,0)=0.9194034557462105

xor(0,1)=0.8913291572885467

xor(0,0)=0.0922342035736988

1&&1=0.8712088309977442

1&&0=0.08891005182518963

0&&1=0.09297532089700676

0&&0=0.009538209942478315

D:\vipro\aityros\aiprogs\neurons\Exe>pause Press any key to continue. . .

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

24.4.Историческая перспектива

Есть люди, которые утверждают, что, когда Розенблатт представил концепцию перцептрона общественности, Минский (Minsky) тут же набросился на него, очень грубо и переходя на личности, включая даже выход на связь с каждой из групп, финансировавших разработки Розенблатта, для то­ го, чтобы рассказать о нём как о шарлатане, в надежде уничтожить Розенблатта как специалиста

иобрезать финансирование его исследований в области нейросетей. Как я уже сказал, я не имел сча стья знать Розенблатта, но я хорошо знаю Минского (я интервьюировал его, когда подрабатывал га зетчиком), и я уверен, что подобная клевета против Минского – попросту неправда. То, что Минский

иего сотрудник Паперт (Papert) сделали – это указали на слабость в теории о том, что интеллект мо жет появиться из одного лишь обучения нейросети. На самом деле Минский практически продемон стрировал теорему о том, что нейросеть не может научиться делать определённые вещи; это ограни

чение не относится исключительно к искусственным нейросетям; есть вещи, которым не могут нау читься и наши естественные нейросети: на обложке книги Минского («Перцептроны» (Perceptrons))

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

164

Глава 25: Альфа­бета обрезка

Манкала (Mancala) – это семейство очень популярных в Африке и Азии настольных игр; это игра подсчёта и захвата. Самой известной на Западе игрой этого семейства является Калах. Игры Манкалы играют во многих африканских и азиатских обществах роль, сравнимую с ролью шахмат на Западе. Они также популярны в Индии, особенно среди тамилских женщин.

В том варианте Манкала, который мы собираемся изучать, на доске имеется

набор лунок, расположенных в два ряда, по одному на каждого игрока. лунки называются ямы, горшки или дома. Два больших отверстия на концах доски, на

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

В процессе посева все семена из одной лунки перекладываются одно за другим во все после дующие лунки по кругу. В зависимости от содержимого каждой засеянной лунки, игрок может захва тить семена с доски. Если отверстие содержит меньше 3 семян, игрок может захватить его содержи мое, также как и семечко, которое он собирался положить в это отверстие. Захваченные семена от правляются в склад игрока. Игра заканчивается, если один игрок захватит как минимум на десять се мян больше, чем его оппонент. Игра также заканчивается, если на стороне одного из игроков не ос танется семян. В любом случае, игрок, который захватит больше семян выигрывает.

25.1.Генерирование хода

Самые нежно любимые игры – это те, в которых один оппонент выставлен против другого, в бит ве умов. Однако я хотел бы указать на то, что даже в подобных играх Эраст Фандорин (Erast Fandorin) всегда выигрывал, как вы можете убедиться, прочитав «Пиковый валет» (The Jack of Spades) [за автор

ством Б. Акунина – прим. пер.]. Однако, компьютеры не настолько удачливы, как статский советник; по этому программистам нужен инструмент для анализа игры; этим инструментом является дерево ми нимакса (см. рис. 10.1). В подобной диаграмме игрок называется Maximizer – Максимизатор, в то время как его противник называется Minimizer – Минимизатор. Во время анализа подразумевается, что Максимизатор будет стремиться получить максимальное значение оценочной функции, отсюда и название; минимизатор пытается добиться от оценочной функции минимального значения. Если го ворить более полно, дерево, подобное представленному на рис. 10.1, не используется. Чтобы понять почему, давайте предположим, что максимизатор анализирует ход B на нижеприведённом дереве. Он знает, что минимизатор сделает ход F, так как F – это контрход наименьшего веса. Таким образом он заключает, что B с его точки зрения стоит 5; теперь он переходит к анализу C; когда он определит, что H=3, он может отложить поиск, так как ход в C будет стоить самое большее 3, а у него уже есть 5 от хода B. Этот процесс пропуска веток вроде I и J называется альфа обрезка. Во время рассуждений с точки зрения минимизатора, всё, что нужно сделать – это инвертировать сигнал оценочной функ ции и применить тот же самый алгоритм, который был использован в случае максимизатора; в этом случае, пропуск веток называется бета обрезка. Наконец, если узел является листком, оценка произ водится с помощью статической функции, то есть, функции, которая не нисходит по веткам.

165

Реализация стратегической игры – сложная задача. Для того, чтобы выполнить это, мы сохраним генерацию хода в отдельном классе, так что сложность самой игры не будет пересекаться с нашими стратегическими рассуждениями. Создайте новый консольный проект.

Project Name: kalahGame

UI Strategy: console

Постройте приложение для того, чтобы вставить класс main в дерево проекта. Затем создайте класс mv выбором пункта New in New Package в меню задач IDE.

% Файл mv.cl class mv

open core domains

side= a;b.

board= none ; t(side, integer LastMove, integer Pot, integer Pot, integer* Brd).

predicates

prtBoard:(board) procedure (i). newBoard:(side, board) procedure (i, o). addPot:(side, integer, integer, integer,

integer, integer) procedure (i,i,i,i, o,o). changeSides:(side, side) procedure (i, o). sowing:(side, integer, integer, positive,

integer, integer, integer*,

board) procedure (i, i, i, i, i, i, i, o). sow:(integer, board, board) procedure (i,i,o). play:(board, board) nondeterm (i, o). stateval:(board, integer) procedure (i, o).

end class mv

% Файл mv.pro implement mv

open core clauses

prtBoard(t(S, LM, P1, P2, [I0, I1, I2, I3, I4, I5, I6, I7])) : !, stdio::write("Move: ", LM), stdio::nl,

if S= a then T= "a" else T= "b" end if, stdio::writef(" %4d %4d %4d %4d\n", I3, I2, I1,I0), stdio::writef("%4d %4d %s\n", P1, P2, T), stdio::writef(" %4d %4d %4d %4d\n", I4, I5, I6, I7).

prtBoard(_) : stdio::write("None\n").

newBoard(Side, t(Side, 1, 0, 0, [6,6,6,6, 6,6,6,6])).

addPot(a, C, P1, P2, P1+C+1, P2) : !. addPot(b, C, P1, P2, P1, P2+C+1).

changeSides(a, b) : !. changeSides(b, a).

sow(I, t(Side, _LastMove, P1, P2, B), NewBoard) :

166

J= I rem 8,

Counts= list::nth(J, B), !, list::setNth(J, B, 0, BA), K= (J+1) rem 8,

sowing(Side, J, Counts, K, P1, P2, BA, NewBoard). sow(_, T, T).

sowing(S, LM, N, K, P1, P2, BA, NuB) : N>0, C= list::nth(K, BA),

C > 0, C < 3, !, list::setNth(K, BA, 0, BB), J= (K+1) rem 8,

addPot(S, C, P1, P2, PP1, PP2), sowing(S, LM, N 1, J, PP1, PP2, BB, NuB).

sowing(S, LM, N, K, P1, P2, BA, NuB) : N > 0, !, list::setNth(K, BA, list::nth(K, BA) + 1, BB), J= (K+1) rem 8,

sowing(S, LM, N 1, J, P1, P2, BB, NuB).

sowing(S, LM, _, _, P1, P2, BB, t(S1, LM, P1, P2, BB)) :

changeSides(S, S1).

stateval(t(_, _, P1, P2, _), P2 P1) : !. stateval(_, 0).

play(t(a, LM, P1, P2, L), X) : list::nth(0, L) > 0, sow(0, t(a, LM, P1, P2, L), X).

play(t(a, LM, P1, P2, L), X) : list::nth(1, L) > 0, sow(1, t(a, LM, P1, P2, L), X).

play(t(a, LM, P1, P2, L), X) : list::nth(2, L) > 0, sow(2, t(a, LM, P1, P2, L), X).

play(t(a, LM, P1, P2, L), X) : list::nth(3, L) > 0, sow(3, t(a, LM, P1, P2, L), X).

play(t(b, LM, P1, P2, L), X) : list::nth(4, L) > 0, sow(4, t(b, LM, P1, P2, L), X).

play(t(b, LM, P1, P2, L), X) : list::nth(5, L) > 0, sow(5, t(b, LM, P1, P2, L), X).

play(t(b, LM, P1, P2, L), X) : list::nth(6, L) > 0, sow(6, t(b, LM, P1, P2, L), X).

play(t(b, LM, P1, P2, L), X) : list::nth(7, L) > 0, sow(7, t(b, LM, P1, P2, L), X).

end implement mv

Теперь вы готовы реализовать основной класс, который будет искать в дереве игры наилучший

ход.

implement main /* kalahGame */ open mv

clauses

classInfo("kalahGame", "1.0"). class predicates

maxeval:( mv::board, integer, integer,

integer, mv::board, integer) procedure (i, i, i, i, o, o). mineval:( mv::board, integer, integer,

integer, mv::board, integer) procedure (i, i, i, i, o, o). bestMax:( mv::board*, integer, integer, integer,

167

mv::board, integer) determ (i, i, i, i, o, o). bestMin:( mv::board*, integer, integer, integer,

mv::board, integer) determ (i, i, i, i, o, o). betaPruning:( mv::board*, integer, integer, integer,

mv::board, integer, mv::board, integer) procedure (i, i, i, i, i, i, o, o).

alphaPruning:( mv::board*, integer, integer, integer, mv::board, integer, mv::board, integer) procedure (i, i, i, i, i, i, o, o).

clauses

maxeval(Pos, LookAhead, Alpha, Beta, Mov, Val) : LookAhead > 0,

Lcs = [P || play(Pos, P)],

bestMax(Lcs, LookAhead 1, Alpha, Beta, Mov, Val), ! ; stateval(Pos, Val), Mov= none.

bestMax([Lnc|Lncs], LookAhead, Alpha, Beta, BestMove, BestVal) : !, mineval(Lnc, LookAhead, Alpha, Beta, _, Val),

betaPruning(Lncs, LookAhead, Alpha, Beta, Lnc, Val, BestMove, BestVal).

betaPruning([], _, _, _, Lnc, Val, Lnc, Val) : !. betaPruning(_, _, _Alpha, Beta, Lnc, Val, Lnc, Val) :

Val > Beta, !.

betaPruning(Lncs, LookAhead, Alpha, Beta, Lnc, Val, MLnc, MVal) : if Val > Alpha then NewAlpha= Val

else NewAlpha= Alpha end if,

if bestMax(Lncs, LookAhead, NewAlpha, Beta, Lnc1, Val1), Val1 > Val then MLnc= Lnc1, MVal= Val1

else MLnc= Lnc, MVal= Val end if.

mineval(Pos, LookAhead, Alpha, Beta, Mov, Val) : LookAhead > 0,

Lcs = [P || play(Pos, P)],

bestMin(Lcs, LookAhead 1, Alpha, Beta, Mov, Val), ! ; stateval(Pos, Val), Mov= none.

bestMin([Lnc|Lncs], LookAhead, Alpha, Beta, BestMove, BestVal) : !, maxeval(Lnc, LookAhead, Alpha, Beta, _, Val),

alphaPruning(Lncs, LookAhead, Alpha, Beta, Lnc, Val, BestMove, BestVal).

alphaPruning([], _, _, _, Lnc, Val, Lnc, Val) : !.

alphaPruning(_, _, Alpha, _Beta, Lnc, Val, Lnc, Val) : Val < Alpha, !. alphaPruning(Lncs, LookAhead, Alpha, Beta, Lnc, Val, MLnc, MVal) :

if Val < Beta then NewBeta= Val else NewBeta= Beta end if,

if bestMin(Lncs, LookAhead, Alpha, NewBeta, Lnc1, Val1), Val1 < Val then MLnc= Lnc1, MVal= Val1

else MLnc= Lnc, MVal= Val end if.

class predicates

readMove:(board, board) procedure (i, o). legalMove:(core::positive, board) determ. game:(board, integer) procedure (i, i). endGame:(board) determ (i).

168

announceWinner:(integer) procedure (i).

clauses

legalMove(I, t(a, _LM, _P1, _P2, X)) : I >= 0, I < 4,

list::nth(I, X) > 0.

readMove(Pos, ReadPos) :

stdio::write("Present situation: "), stdio::nl, prtBoard(Pos),

%stdio::write("Your move: "), SR= stdio::readLine(), trap(I1= toTerm(SR), _, fail), stdio::nl,

legalMove(I1, Pos), sow(I1, Pos, ReadPos), prtBoard(ReadPos), !.

readMove(Pos, ReadPos) : stdio::write("Something failed"), stdio::nl, readMove(Pos, ReadPos).

endGame(X) : stateval(X, V), math::abs(V) > 10, !. endGame(t(a, _LM, _P1, _P2, [I0, I1, I2, I3|_])) :

I0 < 1, I1 < 1, I2 < 1, I3 < 1, !.

endGame(t(b, _LM, _P1, _P2, [_I0, _I1, _I2, _I3, I4, I5, I6, I7])) : I4 < 1, I5 < 1, I6 < 1, I7 < 1, !.

game(X, _Val) : endGame(X), !, stateval(X, V), prtBoard(X),

announceWinner(V).

game(none, Val) : stdio::write("End game: ", Val), announceWinner(Val), !.

game(Pos, _Val) : readMove(Pos, NewPos), maxeval(NewPos, 10, 10, 10, BestMove, BestVal), !, game(BestMove, BestVal).

announceWinner(Val) : Val > 0, stdio::write("\n I won!\n", Val), !.

announceWinner(Val) : Val < 0, stdio::write("\n You won!\n", Val), !.

announceWinner(_Val) : stdio::write("\n It is a draw!\n"). run(): console::init(),

newboard(a, B), stateval(B, Val), game(B, Val).

end implement main /* kalahGame */

goal mainExe::run(main::run).

Как и Эраст Фандорин, я не люблю игры; кроме этого, я не обладаю его удачей, что означает, что я всегда проигрываю. Однако я всё же противопоставил свой ум компьютерному и проиграл. Вот на чало игры:

Present situation:

169

170