1

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

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

Моя текущая реализация

%алгоритм минимакса
minmax(S,S,1,0,_).
minmax(S,S,0,1,_).

%игрок
minmax(S1,S2,0,A,L):-
    can(N),
    S is S1 + N,
    S =< S2,
    L1 is L + 1,
    minmax(S,S2,1,R,L1),
    mn(L,T),
    T > R,
    retractall(mn(L,_)),
    asserta(mn(L,R)),
    A is R.
    
%другой игрок
minmax(S1,S2,1,A,L):-
    can(N),
    S is S1 + N,
    S =< S2,
    L1 is L + 1,
    minmax(S,S2,0,R,L1),
    mx(L,T),
    T < R,
    retractall(mx(L,_)),
    asserta(mx(L,R)),
    A is R.

например для игрока я пытаюсь перебрать все доступные значения can(N), после вызова функции minmax идет сравнение с минимумом на текущем уровне и если он больше, то заменяем. Может есть какой-то более простой способ перебрать все элементы и вернуть с текущего уровня минимум-максимум?

p.s. данный алгоритм некорректно работает.

4
  • Приведите пример входных данных и результата. Commented 7 июн. 2021 в 22:14
  • я привел решение, которое работает для меня, вот только странно, что выигрышное число будет обозначаться нулем (пробовал менять мин макс расчеты в конце, но это ничего не меняло). Commented 8 июн. 2021 в 6:15
  • Ваш вопрос остался неясным для всех остальных. Но если вы решили ваши проблемы, то хорошо. Commented 8 июн. 2021 в 7:01
  • Если интересно, то добавил немного пояснения по тому как следует запускать предикат. Алгоритм лишний раз в конце вызывает для одного значения поиск максимума, но мне кажется это не страшно тк в целом вроде все нормально работает (тестил на мн-ве различных входных значений). Commented 8 июн. 2021 в 10:32

1 ответ 1

1
%кто быстрее всех набрал сумму
minmax(S,S,_,_,1,_,0).
minmax(S,S,_,_,0,_,1).

%ход игрока
minmax(S1,S2,L,[H|T],R1,V,0):-
    S is S1 + H,
    S =< S2,
    minmax(S,S2,L,L,R,[],1),
    minmax(S1,S2,L,T,R1,[R|V],0),!.

%случай когда число не подошло у игрока
minmax(S1,S2,L,[H|T],R,V,0):-
    S is S1 + H,
    S > S2,
    minmax(S1,S2,L,T,R,V,0),!.

%ход второго игрока
minmax(S1,S2,L,[H|T],R1,V,1):-
    S is S1 + H,
    S =< S2,
    minmax(S,S2,L,L,R,[],0),
    minmax(S1,S2,L,T,R1,[R|V],1),!.

%случай когда число не подошло у второго игрока
minmax(S1,S2,L,[H|T],R,V,1):-
    S is S1 + H,
    S > S2,
    minmax(S1,S2,L,T,R,V,1),!.

%достигли конца на текущем уровне
minmax(_,_,_,[],R,V,0):-
    min_list(V,R),!.

minmax(_,_,_,[],R,V,1):-
    max_list(V,R),!.

Тут приведено решение, которое сегодня пришло в голову ну и оно в принципе решило мою проблему.

UPD: чтобы корректно все работало запускать следует так:

minmax([список значений],конечная сумма,[выбранное число из списка значений],ответ,1). 

в качестве ответа получим 1 если выбранное число подходит для текущего хода и 0 если не подходит.

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.