Алгоритм получения наилучшего варианта в игре мексиканский поезд

@КАВ · Регистрация: 16.04.2016

Студворк — интернет-сервис помощи студентам

Всех приветствую. Помогите пожалуйста написать хороший алгоритм игры бота в сто одно при игре вдвоём.
Порядок хода карт очень важен, т.е если, к примеру, у меня на столе будет десять пик и я сначала
схожу пиковой шестёркой, затем пиковой семёркой, то я уже не смогу сходить трефовой
шестёркой и трефовой девяткой, которые у меня есть, поэтому сначала мне нужно сходить
пиковой семёркой, затем пиковой шестёркой, затем трефовой шестёркой а затем трефовой
девяткой.
Согласно правилам, которыми я руководствовался при написании этой игры, при игре вдвоём бот
может продолжать ход, если он сходил (или он раздаёт карты в начале раунда и на столе лежит
одна из этих карт) пятёркой, шестёркой, семёркой, тузом и пиковым королём. Если начала раунда
и игрок, который ходит первым, не сходил не одной картой, т.е на столе нету карт, игрок может
ходить любой картой.
Если игрок заказывает масть дамой, то он не может ходить, пока не наступит очередь его хода и
пока не закажет масть. Если же другой игрок заказал какую-то масть то только игрок, чей ход
наступил после него, может ходить дамой любой масти или любой картой заказанной масти. В
остальных случаях игрок может ходить картой той же масти или того же номинала, что и
последняя карта, которой предыдущий игрок сходил. Если игрок не может сходить не одной
картой, он берёт карту из колоды и, если всё ещё нечем ходить, пропускает ход, кроме случая,
когда последняя карта, которой он сходил, шестёрка (в этом случае он берёт карту из колоды до
тех пор, пока не найдётся карта, которой можно будет ходить). Если в колоде нету карт, она
перетасовывается из тех карт, которые лежат на столе, кроме последней карты.
Раунд выигрывает тот, кто первый останется без своих карт. Игру проигрывает тот, у кого больше,
чем сто одно очко (несмотря на количество игроков, в этой игре есть только один победитель).
Если у игрока ровно сто одно очко, его очки обнуляются.
Если игрок заканчивает дамой, он теряет 20 очков, за исключением пиковой дамы, в результате
которой он теряет 40 очков. Если же после окончания раунда у игрока остаётся только одна дама,
он получает 20 очков, за исключением пиковой дамы, в результате которой он получает 40 очков.
Очки на картах: 2:9, 10 - столько же очков, каков их номинал, валет- два очка, дама - три очка,
король - четыре очка, туз - одиннадцать очков.
Исходя из выше написанного основная задача найти наилучший вариант ходов для бота, в результате
которого у бота в сумме на всех картах останется минимальное количество очков (оставлять одну
даму, не смотря на правила, допускается, поскольку на самом деле ситуация, при которой бот
заканчивает дамой, происходит не часто, поэтому для простоты можно считать, что в этом случае
сумма очков равна 3) при условии, что у бота есть как минимум одна карта, после которой он
может продолжить ход и которой он может ходить. Если же у бота есть хотя бы одна карта,
которой он может ходить, но после которой он не может продолжить ход, мой алгоритм очень
простой: Бот ходит той картой, которая отнимает у него наибольшее количество очков при этом,
по возможности, стараясь оставить даму напоследок, чтобы она отняла у него очки. Если же даму
оставить не удаётся, он заказывает ту масть, карта которой у бота заберёт максимальное
количество очков, хотя и здесь возникают проблемы, т.е и в этом случае мой алгоритм не может
определить наилучшую последовательность карт, если она возможна, в результате которой у бота
в сумме на картах останется минимальное количество очков, поэтому и в этом случае, конечно,
мне тоже будет очень нужна Ваша помощь.
В результате алгоритм должен вернуть список, который содержит списки вариантов ходов бота. В
этих списках должны быть индексы тех карт в списке карт, которые есть у бота и которыми можно
ходить. Ещё можно, если это будет проще, чтобы алгоритм сразу вернул список с индексами карт
бота, которыми можно ходить.
Например, если у бота есть шестёрка бубны, шестёрка червы, семёрка червы и девятка бубны, а
на столе лежит десятка червы, Алгоритм должен мне вернуть три списка с индексами карт бота,
которыми можно ходить, поскольку существует только три варианта хода игрока в этой ситуации.
В первом списке должны быть индексы 2, 1, 0, 3 (семёрка червы, шестёрка червы, шестёрка бубны
и девятка бубны), во втором - 1, 0, 3(шестёрка червы, шестёрка бубны и девятка бубны), в третьем
- 1, 2 (шестёрка червы и семёрка червы). Или же алгоритм мне должен вернуть просто список с
индексами 2, 1, 0, 3 (семёрка червы, шестёрка червы, шестёрка бубны и девятка бубны), т.к это
наилучший вариант хода в этой ситуации.
Не смотря на то, что программа разрабатывается на java, я с огромным удовольствием и благодарностью приму алгоритм на любом языке программирования. Заранее благодарю всех за помощь.

@MLPMan · 04.03.2019, 07:03

Не по теме:

Ааа, кажется, это эта игра, которую на улице почему-то называли "бридж". Однажды даже недоразумение вышло, из-за путаницы в названиях игр.

Правила, видать, изменчивы в разных версиях, но не суть. Сначала нужно резюмировать все правила хода. Итак, можно ходить последовательностью карт, которая начинается с карты такой масти, что лежит на столе, а каждая следующая в последовательности должна быть одной масти, либо одного достоинства с предыдущей. Покуда карт не много, перебор сработает. Берём подходящую первую карту, и ставим в начале последовательности, потом рекурсивно перебираем оставшиеся, и добавляем следующие карты в последовательность, так пока в руке останутся только неподходящие кандидаты следующей карты. Так можно собрать все допустимые на этом ходу последовательности, чтобы выбрать лучшую. Но, насколько я помню, там есть карты с особым поведением, поэтому логика выбора будет немного сложнее.

Общие советы: сначала следует закодить механизм, который будет отличать корректный ход от невозможного. Пользуясь этим, бот вычисляет, что он может сделать. Лучше, чтобы API был максимально прикладным. В частности, например, идентифицировать карты лучше не по индексу, а по значению (масть+достоинтсво). Технически это не важно, но так будет легче думать.

@Shamil1 · 04.03.2019, 13:52

Карт мало. Поэтому все возможные цепочки получаем полным перебором. Цепочка может заканчиваться ходом "взять карту из колоды".

@КАВ · 04.03.2019, 14:54 **[ТС]**

Всех приветствую. Как я понял, поскольку тема про игру сто одно была удалена, обсуждение переместилось в эту тему. Перебор, это, наверное, хорошая идея, но где гарантия, что именно первая карта даст мне наилучший вариант? А может, к примеру, для наилучшего варианта мне нужно сходить пятой картой в списке, затем нулевой, затем первой, а затем четвёртой? К тому же может быть такая ситуация,что у игрока будет очень много карт, к примеру 26. Конечно, такая ситуация будет возникать очень и очень редко, но алгоритм должен корректно и быстро отрабатывать и в такой ситуации. По поводу правил, человек может ходить картой этой же масти или достоинства или любой дамой, даже если на столе лежит только одна карта. Что касается проверки корректности хода, это уже очень давно у меня реализовано и отлажено, осталось только получить наилучшую последовательность ходов бота. Кстати этот алгоритм подойдёт для игры мексиканский поезд, поскольку задача тоже заключается в получении наилучшей последовательности ходов, в результате которой у меня останется наименьшее количество костей, которые я уже не смогу добавить в свой поезд. Заранее благодарю всех за помощь.

@Shamil1 · 04.03.2019, 15:26

Сообщение от КАВ

Перебор, это, наверное, хорошая идея, но где гарантия, что именно первая карта даст мне наилучший вариант? А может, к примеру, для наилучшего варианта мне нужно сходить пятой картой в списке, затем нулевой, затем первой, а затем четвёртой?

Значит, где-то в списке вариантов будет и такая последовательность.

Одна функция находит все варианты ходов-цепочек, другая выбирает из них один ("самый лучший").

Не по теме:

Сообщение от КАВ

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

Текст первого сообщение в той теме был точно таким же, как в этой. В этой теме уже был один ответ. Поэтому та тема удалена как дубль.

@КАВ · 04.03.2019, 16:47 **[ТС]**

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

@MLPMan · 04.03.2019, 21:21

Java
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
package testings;
 
import java.util.*;
 
enum Suit {S("Spade"),C("Club"),D("Diamond"),H("Heart");
    String val;
 
    private Suit(String val) {
        this.val = val;
    }
 
    @Override
    public String toString() {
        return val;
    }
            
}
 
class Card {
    Suit suit;
    int value;
 
    public Card(Suit s,int v) {
        suit=s;
        value=v;
    }
 
    public boolean compatible(Card previous) {
    return (previous.suit==this.suit || previous.value==this.value);
    }
 
    @Override
    public int hashCode() {
        int hash = 5;
        hash = 37 * hash + Objects.hashCode(this.suit);
        hash = 37 * hash + this.value;
        return hash;
    }
 
    @Override
    public boolean equals(Object obj) {
        if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
        final Card other = (Card) obj;
        if (this.suit != other.suit) return false;
        if (this.value != other.value) return false;
        return true;               
    }        
 
    @Override
    public String toString() {
        return "["+String.valueOf(value)+" of "+suit.toString()+"s] ";
    }
}
 
public class Testings {
 
    public static void main(String[] args) {        
        test1();
    }
    
    /**
     * 
     * @param start Начало последовательности, 1 или более карт
     * @param pretends Рука
     * @param collectTo Куда сохранять возможные варианты
     */
        static void collectNewSequence(List<Card> start, Set<Card> pretends, Set<List<Card>> collectTo) {                
        Set<Card> tmpHand = new HashSet();
        tmpHand.addAll(pretends); // Копия руки, чтобы можно было удалять карты, не испортив оригинал
        Card last = start.get(start.size()-1); // Какую карту можно класть следующей, зависит от последней
        for (Card c : pretends) {
            if (last.compatible(c)) {                               
                            List<Card> newSec = new ArrayList();
                            // Создаём новую последовательность, как копию старой, но с добавлением новой карты:
                            for (int i=0; i<start.size(); i++) {
                                newSec.add(start.get(i));
                            }
                            newSec.add(c);                            
                            tmpHand.remove(c); // Удаляем эту карту из виртуальной руки (перенесли)
                            collectTo.add(newSec); // Запомним последовательность                            
                            collectNewSequence(newSec, tmpHand, collectTo); // Проверим, есть ли варианты для последовательности удлиниться ещё, при оставшейся руке
            }
        }
    }
 
    static void debugCards(List<Card> l) {
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<l.size(); i++) {
            sb.append(l.get(i).toString());
            sb.append(",");
        }
        System.out.println(sb.toString());      
    }
 
    static void test1() {
        List<Card> c = new ArrayList();
        Set<Card> hand = new HashSet();
        Set<List<Card>> variants = new HashSet();                
        c.add(new Card(Suit.H,6)); // Первая карта последовательности (она и последняя) будет той, что лежит на столе сначала
        hand.add(new Card(Suit.S, 6));
                hand.add(new Card(Suit.D, 6));
                hand.add(new Card(Suit.D, 7));
                hand.add(new Card(Suit.H, 9));
                hand.add(new Card(Suit.C, 10));
                hand.add(new Card(Suit.C, 7));
                collectNewSequence(c, hand, variants);
        for (List<Card> li : variants) {
            debugCards(li);
        }
    }    
}

@КАВ · 05.03.2019, 01:54 **[ТС]**

Огромное Вам спасибо за Ваш алгоритм. Я пока что его не тестировал,поэтому прошу простить меня за очень глупые вопросы, но правильно ли я понял по коду, что если, к примеру, последняя карта на столе девятка бубны, а в моей руке будет шестёрка бубны, семёрка бубны, шестёрка червы и девятка червы, то последовательность,которая для данных карт в руке наилучшая (семёрка бубны, шестёрка бубны, шестёрка червы и девятка червы) показана не будет, поскольку карта шестёрка бубны, т.к ей можно ходить, будет удалена на первой итерации? Если я не прав, и она всё же будет показана среди всех вариантов,прошу простить меня пожалуйста.

@Shamil1 · 05.03.2019, 10:41

MLPMan,
Карт в руке немного, поэтому линейный поиск в списке, вероятно, будет лучше, чем HashSet.
Для возвращаемых последовательностей лучше использовать неизменяемый односвязный список. Тогда не придётся копировать списки внутри цикла.

@КАВ · 05.03.2019, 16:25 **[ТС]**

Интересно, что значит карт немного, т.е при каком максимальном значении n линейный поиск будет оптимальным. По поводу списков, мне как раз удобнее, чтобы каждый вариант хранился в отдельном списке, чем все варианты будут в одном односвязном списке, поскольку тогда я смогу понять,где какая последовательность и с ней работать. Очень жаль что,как я понял,алгоритм не делает перестановок, т.е как я писал ранее, не всегда первая карта в списке, которой можно ходить, даст мне наилучшую последовательность хода, т.е к примеру может быть так, что, к примеру, сначала нужно ходить первой картой, хоть нулевой картой тоже можно ходить, потом третьей, потом второй, а потом нулевой, но может кто-то поможет написать алгоритм, который учитывает перестановки карт, если я прав по поводу этого алгоритма. Перестановки актуальны в тех случаях, когда я могу ходить теми картами, после которых мой ход продолжается, т.е у которых, как это у меня реализовано, skypeturn >=0 (если он больше единицы, то игрок x берёт из колоды skypeturn карт и пропускает ход, если равен единице, просто пропускает ход, а если нулю, - то ход игрока y продолжается несмотря на то, что в игре больше двух игроков, хотя я буду использовать этот алгоритм только при игре вдвоём, т.к только тогда он будет иметь наибольший смысл). В любом случае огромное спасибо MLPMan и за этот вариант и за то,что алгоритм написан на java, поскольку для меня это всё же более предпочтительный язык, т.к на нём разработана эта игра, хотя python тоже подойдёт. Этот алгоритм, особенно если он будет учитывать, перестановки карт, можно с лёгкостью применить и в игре мексиканский поезд, поскольку в этой игре тоже стоит задача получения всех вариантов ходов.

@Shamil1 · 06.03.2019, 13:01

Сообщение от КАВ

что значит карт немного, т.е при каком максимальном значении n линейный поиск будет оптимальным.

Предположу, что для 10 карт линейный поиск будет лучше, а для 20 карт разница будет незначительной.

Сообщение от КАВ

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

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

@КАВ · 06.03.2019, 15:29 **[ТС]**

Вы имеете ввиду под односвязным списком класс LintList?

@Shamil1 · 06.03.2019, 16:07

Неизменяемый список. Например, fj.data.List<A> из Functional Java.

@КАВ · 24.03.2019, 15:14 **[ТС]**

Всех приветствую. Как я ранее писал, предложенный алгоритм мне не подошёл, поскольку он показывал не все варианты ходов. Поэтому у меня дошли руки написать свой алгоритм (пока что на python для мексиканского поезда), который, вроде, работает, хотя потом он будет адаптироваться под игру сто одно на java, поскольку он не чем, кроме условия для проверки корректности хода, не отличается). Может быть у кого-то будут идеи, как его оптимизировать хотя бы на java, при большом количестве карт (поскольку в одном из моих проектов я заметил, что моя программа под android начинает тормозить, если количество итераций >=5000, я боюсь, что мой алгоритм при большом количестве карт на java будет использовать >=5000 итераций). Да и в плане структур, т.е что лучше будет использовать в данном алгоритме при его реализации на java (List, Set, LintList, Stack) и т.д тоже было бы неплохо его оптимизировать. Заранее благодарю всех за идеи и выкладываю здесь мой алгоритм (может он когда-то кому-то пригодится и поможет).

Python
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
class die: #Класс для кости (для меньшего числа проверок, два аргумента хранятся в картеже)
 def __init__(self,*a):
#для правильной проверки того,что фишка подходит, делаем так, чтобы первое значение фишки было наименьшее.
  if a[0]>a[1]: a=a[1],a[0]
  self.a=a
 
def getvariants(number,a,b,c): #Сам алгоритм для получения всех вариантов ходов.
 variants=0 #переменная, которая покажет, можем ли мы добавлять ещё что-то, или нужно добавлять данную последовательность в список с последовательностями.
 if len(a)==0: # Если мы нашли вариант, в результате которого все фишки израсходованы, добавляем этот список в последовательность и останавливаем выполнение алгоритма
  b.append(c)
  return
 for die in range(len(a)):
  if a[die].a[0]==number or a[die].a[1]==number: #Если эта фишка нам подходит, прибавляем к количеству вариантов 1, добавляем её в нашу последовательность new_list_0 (копия списка c), удаляем её из new_list (копия списка a),заменяем номер на противоположную часть фишки, т.е к примеру если у нас номер 6,а фишка 1,6, то номер будет равен 1 и рекурсивно вызываем эту функцию с другими параметрами.
   variants=variants+1
   new_list=a.copy()
   new_list_0=c.copy()
   del new_list[die]
   new_list_0.append(a[die])
   getvariants(a[die].a[(a[die].a.index(number)+1)%2],new_list,b,new_list_0)
#Если завершилась последняя итерация, а у нас в списке больше нечем ходить и длинна нашей последовательности больше нуля,добавляем её в список последовательностей.
  if die==len(a)-1 and variants==0 and len(c)>0: b.append(c)
 
a=[] #Тестируем наш алгоритм.
getvariants(6,[die(6,6),die(1,6),die(1,1),die(1,2)],a,[])
a.sort(key=len)
len(a[-1])
#Длинна самого длинного варианта - 4, как и должно быть.

@Shamil1 · 25.03.2019, 09:33

Сообщение от КАВ

new_list=a.copy() new_list_0=c.copy()

Я писал, как избежать копирования списков.

Ещё можно удалять карту из списка перед рекурсивным вызовом и добавлять её обратно после рекурсивного вызова (для изменяемых списков).

@КАВ · 25.03.2019, 14:46 **[ТС]**

По поводу списков я понял, но хотелось бы уточнить, правильно ли я понимаю, что эта возможность появилась в java 8 и для использования этого списка нужно заменить импорт в android studio s ArrayList на fj.data.List? Также я не понял, как я смогу избежать копирования списка, если я буду использовать fj.data.List, т.е какой метод там заменяет копирование списков,позволяя избежать физическое копирование памяти?

@Shamil1 · 25.03.2019, 14:58

Сообщение от КАВ

По поводу списков я понял, но хотелось бы уточнить, правильно ли я понимаю, что эта возможность появилась в java 8

Эта возможность была всегда. Такой класс можно написать в любой версии java (там кода на пару экранов). Когда появилась библиотека fj.data.List и для какой версии её можно использовать, я не знаю.

@КАВ · 25.03.2019, 14:58 **[ТС]**

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

@Shamil1 · 25.03.2019, 15:52

Сообщение от КАВ

По поводу удаления карты до рекурсивного вызова и её вставки после рекурсивного вызова

Этот подход работает для временных списков. Например, для списка карт, которые у меня есть на руках ("для списка с моими картами"). Тогда в цикле для всех карт из этого списка 1) удаляем из списка 2) рекурсивный вызов 3) добавляем в список (чтобы в начале следующей итерации цикла список опять был полный).

Этот подход не работает для "постоянных" списков. То есть, тех, которые будут использоваться за пределами нашей функции. Например, для цепочки карт хода ("для списка с очередным вариантом").

Сообщение от КАВ

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

Вы можете перебирать карты с конца списка и вставлять всегда в конец списка.
Или не удалять карты из списка, а помечать их как удалённые.

@КАВ · 25.03.2019, 23:23 **[ТС]**

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

Python
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
class die:
 def __init__(self,*a):
  if len(a)!=2:
   self=None
   return
  if a[0]>a[1]: a=a[1],a[0]
  self.a=a
 
def getvariants(number,a,b,c):
 variants=0
 if len(a)==0:
  b.append(c)
  return
 for die in range(len(a)-1,-1,-1):
  die0=a[die]
  if die0.a[0]==number or die0.a[1]==number:
   variants=variants+1
   new_list=c.copy()
   del a[die]
   new_list.append(die0)
   getvariants(die0.a[(die0.a.index(number)+1)%2],a,b,new_list)
   a.append(die0)
  if die==len(a)-1 and variants==0 and len(c)>0: b.append(c)
 
a=[]
getvariants(6,[die(6,6),die(1,6),die(1,1),die(1,2)],a,[])
a.sort(key=len)

Новые блоги и статьи Все статьи Все блоги /
Отправка уведомления на почту при изменении наименования справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере изменения наименования справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной записи. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .	Контроль уникальности заводского номера - вариант №2 Maks 24.03.2026 В отличие от предыдущего варианта добавлено прерывание циклов, также добавлены новые переменные для сохранения контекста ошибки перед прерыванием цикла: Процедура ПередЗаписью(Отказ, РежимЗаписи,. . .
SDL3 для Desktop (MinGW): Вывод текста со шрифтом TTF с помощью библиотеки SDL3_ttf на Си и C++ 8Observer8 24.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-text-sdl3-c. zip finish-text-sdl3-cpp. zip	Жизнь в неопределённости kumehtar 23.03.2026 Жизнь — это постоянное существование в неопределённости. Например, даже если у тебя есть список дел, невозможно дойти до точки, где всё окончательно завершено и больше ничего не осталось. В принципе,. . .	Модель здравоСохранения: работники работают быстрее после её введения. anaschu 23.03.2026 geJalZw1fLo Корпорация до введения программа здравоохранения имела много невыполненных работниками заданий, после введения программы количество заданий выросло. Но на выплатах по больничным это. . .	Контроль уникальности заводского номера - вариант №1 Maks 23.03.2026 Алгоритм контроля уникальности заводского (или серийного) номера на примере документа выдачи шин для спецтехники с табличной частью в конфигурации КА2. Данные берутся из регистра сведений, по. . .

@КАВ 17 / 5 / 0 Регистрация: 16.04.2016 Сообщений: 344

	Алгоритм получения наилучшего варианта в игре мексиканский поезд 04.03.2019, 04:10. Показов 1420. Ответов 20 Метки нет (Все метки) Всех приветствую. Помогите пожалуйста написать хороший алгоритм игры бота в сто одно при игре вдвоём. Порядок хода карт очень важен, т.е если, к примеру, у меня на столе будет десять пик и я сначала схожу пиковой шестёркой, затем пиковой семёркой, то я уже не смогу сходить трефовой шестёркой и трефовой девяткой, которые у меня есть, поэтому сначала мне нужно сходить пиковой семёркой, затем пиковой шестёркой, затем трефовой шестёркой а затем трефовой девяткой. Согласно правилам, которыми я руководствовался при написании этой игры, при игре вдвоём бот может продолжать ход, если он сходил (или он раздаёт карты в начале раунда и на столе лежит одна из этих карт) пятёркой, шестёркой, семёркой, тузом и пиковым королём. Если начала раунда и игрок, который ходит первым, не сходил не одной картой, т.е на столе нету карт, игрок может ходить любой картой. Если игрок заказывает масть дамой, то он не может ходить, пока не наступит очередь его хода и пока не закажет масть. Если же другой игрок заказал какую-то масть то только игрок, чей ход наступил после него, может ходить дамой любой масти или любой картой заказанной масти. В остальных случаях игрок может ходить картой той же масти или того же номинала, что и последняя карта, которой предыдущий игрок сходил. Если игрок не может сходить не одной картой, он берёт карту из колоды и, если всё ещё нечем ходить, пропускает ход, кроме случая, когда последняя карта, которой он сходил, шестёрка (в этом случае он берёт карту из колоды до тех пор, пока не найдётся карта, которой можно будет ходить). Если в колоде нету карт, она перетасовывается из тех карт, которые лежат на столе, кроме последней карты. Раунд выигрывает тот, кто первый останется без своих карт. Игру проигрывает тот, у кого больше, чем сто одно очко (несмотря на количество игроков, в этой игре есть только один победитель). Если у игрока ровно сто одно очко, его очки обнуляются. Если игрок заканчивает дамой, он теряет 20 очков, за исключением пиковой дамы, в результате которой он теряет 40 очков. Если же после окончания раунда у игрока остаётся только одна дама, он получает 20 очков, за исключением пиковой дамы, в результате которой он получает 40 очков. Очки на картах: 2:9, 10 - столько же очков, каков их номинал, валет- два очка, дама - три очка, король - четыре очка, туз - одиннадцать очков. Исходя из выше написанного основная задача найти наилучший вариант ходов для бота, в результате которого у бота в сумме на всех картах останется минимальное количество очков (оставлять одну даму, не смотря на правила, допускается, поскольку на самом деле ситуация, при которой бот заканчивает дамой, происходит не часто, поэтому для простоты можно считать, что в этом случае сумма очков равна 3) при условии, что у бота есть как минимум одна карта, после которой он может продолжить ход и которой он может ходить. Если же у бота есть хотя бы одна карта, которой он может ходить, но после которой он не может продолжить ход, мой алгоритм очень простой: Бот ходит той картой, которая отнимает у него наибольшее количество очков при этом, по возможности, стараясь оставить даму напоследок, чтобы она отняла у него очки. Если же даму оставить не удаётся, он заказывает ту масть, карта которой у бота заберёт максимальное количество очков, хотя и здесь возникают проблемы, т.е и в этом случае мой алгоритм не может определить наилучшую последовательность карт, если она возможна, в результате которой у бота в сумме на картах останется минимальное количество очков, поэтому и в этом случае, конечно, мне тоже будет очень нужна Ваша помощь. В результате алгоритм должен вернуть список, который содержит списки вариантов ходов бота. В этих списках должны быть индексы тех карт в списке карт, которые есть у бота и которыми можно ходить. Ещё можно, если это будет проще, чтобы алгоритм сразу вернул список с индексами карт бота, которыми можно ходить. Например, если у бота есть шестёрка бубны, шестёрка червы, семёрка червы и девятка бубны, а на столе лежит десятка червы, Алгоритм должен мне вернуть три списка с индексами карт бота, которыми можно ходить, поскольку существует только три варианта хода игрока в этой ситуации. В первом списке должны быть индексы 2, 1, 0, 3 (семёрка червы, шестёрка червы, шестёрка бубны и девятка бубны), во втором - 1, 0, 3(шестёрка червы, шестёрка бубны и девятка бубны), в третьем - 1, 2 (шестёрка червы и семёрка червы). Или же алгоритм мне должен вернуть просто список с индексами 2, 1, 0, 3 (семёрка червы, шестёрка червы, шестёрка бубны и девятка бубны), т.к это наилучший вариант хода в этой ситуации. Не смотря на то, что программа разрабатывается на java, я с огромным удовольствием и благодарностью приму алгоритм на любом языке программирования. Заранее благодарю всех за помощь. 0

@MLPMan Кандёхаем веселее! 296 / 330 / 76 Регистрация: 02.10.2012 Сообщений: 2,175
	04.03.2019, 07:03
	Не по теме: Ааа, кажется, это эта игра, которую на улице почему-то называли "бридж". Однажды даже недоразумение вышло, из-за путаницы в названиях игр. Правила, видать, изменчивы в разных версиях, но не суть. Сначала нужно резюмировать все правила хода. Итак, можно ходить последовательностью карт, которая начинается с карты такой масти, что лежит на столе, а каждая следующая в последовательности должна быть одной масти, либо одного достоинства с предыдущей. Покуда карт не много, перебор сработает. Берём подходящую первую карту, и ставим в начале последовательности, потом рекурсивно перебираем оставшиеся, и добавляем следующие карты в последовательность, так пока в руке останутся только неподходящие кандидаты следующей карты. Так можно собрать все допустимые на этом ходу последовательности, чтобы выбрать лучшую. Но, насколько я помню, там есть карты с особым поведением, поэтому логика выбора будет немного сложнее. Общие советы: сначала следует закодить механизм, который будет отличать корректный ход от невозможного. Пользуясь этим, бот вычисляет, что он может сделать. Лучше, чтобы API был максимально прикладным. В частности, например, идентифицировать карты лучше не по индексу, а по значению (масть+достоинтсво). Технически это не важно, но так будет легче думать. 0

@Shamil1 Модератор 3136 / 2283 / 469 Регистрация: 26.03.2015 Сообщений: 8,886
	04.03.2019, 13:52
	Карт мало. Поэтому все возможные цепочки получаем полным перебором. Цепочка может заканчиваться ходом "взять карту из колоды". 0

@КАВ 17 / 5 / 0 Регистрация: 16.04.2016 Сообщений: 344
	04.03.2019, 14:54 [ТС]
	Всех приветствую. Как я понял, поскольку тема про игру сто одно была удалена, обсуждение переместилось в эту тему. Перебор, это, наверное, хорошая идея, но где гарантия, что именно первая карта даст мне наилучший вариант? А может, к примеру, для наилучшего варианта мне нужно сходить пятой картой в списке, затем нулевой, затем первой, а затем четвёртой? К тому же может быть такая ситуация,что у игрока будет очень много карт, к примеру 26. Конечно, такая ситуация будет возникать очень и очень редко, но алгоритм должен корректно и быстро отрабатывать и в такой ситуации. По поводу правил, человек может ходить картой этой же масти или достоинства или любой дамой, даже если на столе лежит только одна карта. Что касается проверки корректности хода, это уже очень давно у меня реализовано и отлажено, осталось только получить наилучшую последовательность ходов бота. Кстати этот алгоритм подойдёт для игры мексиканский поезд, поскольку задача тоже заключается в получении наилучшей последовательности ходов, в результате которой у меня останется наименьшее количество костей, которые я уже не смогу добавить в свой поезд. Заранее благодарю всех за помощь. 0

@КАВ 17 / 5 / 0 Регистрация: 16.04.2016 Сообщений: 344
	04.03.2019, 16:47 [ТС]
	В том то и проблема,что я не знаю, как правильно написать функцию, получающую список всех вариантов, ведь мне нужно сделать все возможные перестановки, а как их правильно сделать, я не знаю. По поводу темы, я продублировал тему в этом разделе, поскольку язык, на котором будет написан этот алгоритм, для меня не очень важен. 0

@КАВ 17 / 5 / 0 Регистрация: 16.04.2016 Сообщений: 344
	05.03.2019, 01:54 [ТС]
	Огромное Вам спасибо за Ваш алгоритм. Я пока что его не тестировал,поэтому прошу простить меня за очень глупые вопросы, но правильно ли я понял по коду, что если, к примеру, последняя карта на столе девятка бубны, а в моей руке будет шестёрка бубны, семёрка бубны, шестёрка червы и девятка червы, то последовательность,которая для данных карт в руке наилучшая (семёрка бубны, шестёрка бубны, шестёрка червы и девятка червы) показана не будет, поскольку карта шестёрка бубны, т.к ей можно ходить, будет удалена на первой итерации? Если я не прав, и она всё же будет показана среди всех вариантов,прошу простить меня пожалуйста. 0

@Shamil1 Модератор 3136 / 2283 / 469 Регистрация: 26.03.2015 Сообщений: 8,886
	05.03.2019, 10:41
	MLPMan, Карт в руке немного, поэтому линейный поиск в списке, вероятно, будет лучше, чем HashSet. Для возвращаемых последовательностей лучше использовать неизменяемый односвязный список. Тогда не придётся копировать списки внутри цикла. 1

@КАВ 17 / 5 / 0 Регистрация: 16.04.2016 Сообщений: 344
	05.03.2019, 16:25 [ТС]
	Интересно, что значит карт немного, т.е при каком максимальном значении n линейный поиск будет оптимальным. По поводу списков, мне как раз удобнее, чтобы каждый вариант хранился в отдельном списке, чем все варианты будут в одном односвязном списке, поскольку тогда я смогу понять,где какая последовательность и с ней работать. Очень жаль что,как я понял,алгоритм не делает перестановок, т.е как я писал ранее, не всегда первая карта в списке, которой можно ходить, даст мне наилучшую последовательность хода, т.е к примеру может быть так, что, к примеру, сначала нужно ходить первой картой, хоть нулевой картой тоже можно ходить, потом третьей, потом второй, а потом нулевой, но может кто-то поможет написать алгоритм, который учитывает перестановки карт, если я прав по поводу этого алгоритма. Перестановки актуальны в тех случаях, когда я могу ходить теми картами, после которых мой ход продолжается, т.е у которых, как это у меня реализовано, skypeturn >=0 (если он больше единицы, то игрок x берёт из колоды skypeturn карт и пропускает ход, если равен единице, просто пропускает ход, а если нулю, - то ход игрока y продолжается несмотря на то, что в игре больше двух игроков, хотя я буду использовать этот алгоритм только при игре вдвоём, т.к только тогда он будет иметь наибольший смысл). В любом случае огромное спасибо MLPMan и за этот вариант и за то,что алгоритм написан на java, поскольку для меня это всё же более предпочтительный язык, т.к на нём разработана эта игра, хотя python тоже подойдёт. Этот алгоритм, особенно если он будет учитывать, перестановки карт, можно с лёгкостью применить и в игре мексиканский поезд, поскольку в этой игре тоже стоит задача получения всех вариантов ходов. 0

@КАВ 17 / 5 / 0 Регистрация: 16.04.2016 Сообщений: 344
	06.03.2019, 15:29 [ТС]
	Вы имеете ввиду под односвязным списком класс LintList? 0

@Shamil1 Модератор 3136 / 2283 / 469 Регистрация: 26.03.2015 Сообщений: 8,886
	06.03.2019, 16:07
	Неизменяемый список. Например, fj.data.List<A> из Functional Java. 0

@КАВ 17 / 5 / 0 Регистрация: 16.04.2016 Сообщений: 344
	25.03.2019, 14:46 [ТС]
	По поводу списков я понял, но хотелось бы уточнить, правильно ли я понимаю, что эта возможность появилась в java 8 и для использования этого списка нужно заменить импорт в android studio s ArrayList на fj.data.List? Также я не понял, как я смогу избежать копирования списка, если я буду использовать fj.data.List, т.е какой метод там заменяет копирование списков,позволяя избежать физическое копирование памяти? 0

@КАВ 17 / 5 / 0 Регистрация: 16.04.2016 Сообщений: 344
	25.03.2019, 14:58 [ТС]
	По поводу удаления карты до рекурсивного вызова и её вставки после рекурсивного вызова, это, на мой взгляд, очень хорошая идея, но правильно ли я понимаю,что во-первых я могу это сделать и для списка с моими картами, и для списка с данной последовательностью, т.е для с писка с очередным вариантом, а во-вторых я должен помнить индекс,откуда я её удаляю, чтобы туда же эту карту и вставить после рекурсивного вызова, поскольку если я её просто добавлю в список, то мой алгоритм будет работать некорректно, поскольку эта карта снова встретится мне на последней итерации. 0