Простые крестики-нолики AI [закрыто]

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



Решения, которые я видел:



(1) Использование минимакса с альфа-бета-обрезкой. Это кажется мне сложным и, возможно, ненужным для такой простой игры? Может быть, это слишком сложно? Если нет, мне нужно будет сделать много жесткого кодирования или я неправильно понял алгоритм?



(2) Напишите свой код, используя стратегию псевдокода из Википедии... Я точно не знаю, как это осуществить. Например, там просто написано "проверьте наличие вилок". Будет ли большинство этих проверок выполняться с помощью массива выигрышных линий и проверки, будут ли они заполнены или что-то в этом роде? Если нет, то может ли кто-нибудь дать мне подсказки о том, какие структуры данных или любые основные советы о том, как реализовать проверки, поставленные в псевдокоде здесь: http://en.wikipedia.org/wiki/Tic-tac-toe#Strategy . Я также видел алгоритмы, которые дают числовое значение квадрату " X "и квадрату "O", а затем используют сумму для определения победителя, но я не вижу, почему это особенно полезно.



Любые другие разумные решения?

727   2  

2 ответов:

Честно говоря, когда имеешь дело с ИИ и эвристикой, самые простые задачи могут очень быстро усложниться. Минимаксный подход даст вам наилучшие результаты, и это не должно быть слишком сложно, учитывая тот факт, что вы внедряете ИИ. Это установленный стандарт с пошаговой игровой логикой на 2 игрока.

Проверьте этот веб-сайт... это дает некоторое хорошее представление о крестиках-ноликах ИИ и минимаксе реализация.

Http://www.ntu.edu.sg/home/ehchua/programming/java/JavaGame_TicTacToe_AI.html

Правка:

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

Edit2:

"более простая реализация" несколько относительна. Минимакс-это стандарт, и, как я уже сказал в комментарии, Вы можете манипулировать эвристикой, чтобы удовлетворить случаи, которые вы ищете...

Я хотел бы рассказать вам самый простой способ, но существует так много переменных, зависящих от внедрения вашей игры в код.

Возьмите предложения, посмотрите на вашу игровую реализацию, а затем посмотрите, что подходит вам лучше всего!

Что является простым для один человек может быть сложным для другого. Я просто пытаюсь дать вам варианты, и Минимакс довольно солидный. Может быть, попробовать настроить его в соответствии с вашими потребностями.

Edit3:

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

9  
2013-04-02 04:16:34

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

Например, вы можете закодировать его следующим образом: 

var turns = {
  "mefirst":{
    "move":0,
    "next":[
      null,
      {
        "move":4,
        "next":[
          null,
          null,
          {"move":8}, // win
          {"move":8}, // win
          null,
          {"move":8}, // win
          {"move":8}, // win
          {"move":8}, // win
          {
            "move":6,
            "next":[
              null,
              null,
       /* AND SO ON... */
    ]
  }
};

Тогда вы можете начать с: 

if( ai_goes_first) {
    game = turns.mefirst;
    makeMove(game.move);
}
else game = turns.themfirst;
playerTurn();

Где playerTurn - это что-то вроде: 

function playerTurn() {
    when player clicks a valid squeare {
        game = game.next[chosenSquare];
        makeMove(game.move);
        if( game.next) playerTurn();
    }
}
3  
2013-04-02 02:37:01

Comments

    Ничего не найдено.
Click here to cancel reply.