INFOMAN брой 21

/*
 IOI2001
Игра Ioiwari
ЗАДАЧА

Игрите със зърна и дупки са известни много отдавна като 
игри от групата Манкала. Тази задача е вариант на такава 
игра, специално разработена за IOI. Играта се играе от 
двама души върху кръгла дъска със седем дупки, разположени 
по края на дъската. Всеки от играчите разполага с допълнителна 
дупка, която наричаме банка. Играта започва, като 20 зърна се 
разпределят случайно в седемте дупки така, че във всяка дупка 
да има най-малко 2 и най-много 4 зърна. Играчите правят ходове 
последователно.  Играчът, който е на ход, избира непразна дупка 
и взема всички зърна от нея в ръката си. Докато има зърна в 
ръката си, играчът извършва следните действия, като започва от 
дупката след изпразнената и обикаля по посока на часовниковата 
стрелка:
ч	При повече от 1 зърно в ръката  Ц ако в дупката има 
5 зърна, взема 1 зърно от нея и го слага в банката си, в противен 
случай поставя 1 зърно от ръката си в дупката. 
ч	При 1 зърно в ръката Ц ако в дупката има от 1 до 4 зърна,  
всички те и зърното от ръката му отиват в банката, в противен 
случай (0 или 5 зърна в дупката) поставя зърното от ръката си в 
банката на противника.

Играта свършва, когато всички дупки се окажат празни. Победител 
е този, който има повече зърна в банката си.

Първият играч винаги има печеливша стратегия. Напишете програма, 
която играе Ioiwari като първи играч и печели. Противникът играе 
оптимално, т.е., щом получи възможност, той ще спечели.  

ВХОД И ИЗХОД

Вашата програма чете от стандартния вход и пише на стандартния изход. 
Тя играе като първи играч, а противникът Ц като втори. Най-напред, 
програмата ви трябва да прочете 1 ред със 7 цели числа Ц първоначалния 
брой зърна във всяка от дупките от 1 до 7 (дупките са номерирани по 
посока на часовниковата стрелка). В началото банките са празни.

Оттук нататък започва самата игра. Вашата програма трябва да играе
 по следния начин:
ч	Ако е неин ред, тя записва номера на дупката за поредния ход. 
ч	Ако е ред на противника, програмата ви прочита номера на 
дупката за поредния ход (тази, която на дадения ход се опразва от 
противника).


 РЕШЕНИЕ:

 Един метод за намиране на оптимална стратегия при игра е строенето на
 дървото на играта и избирането на оптимални ходове. Всеки връх в дървото
 е конфигурация на играта. Корена на дървото е началната конфигурация
 на играта. Наслендниците на даден връх са всички конфигурации
 на които може да се отиде от конфигурацията определена от този връх.
 Лист на дървото е всяка терминална конфигурация.
 Нека дефинираме функция, която описва оптимална стратегия за игра на
 двамата играчи - V(x), kъдето V(x) е максималната разлика на
 печалбата която може да се достигне за дадена конфигурация.
 Стойностите за терминалните конфигурации са нула. На всеки свой
 ход играч 1 се опитва да максимизира своята печалба а на всеки свой
 ход играч 2 се опитва да минимизира печалбата на А. Тогава имаме:

            MAX { Di + V(Ci) }, ako 1 e на ход.
    V(x) =
            MIN { -Di + V(Ci) }, ако 2 е на ход.

    V(x) = 0, ako се намираме в терминална конфигурация.

 Di e печалбата на текущия играч, тя е равна на неговата печалба за
 този ход минус печалбата на опонента му.
 Тези формули описват minimax алгоритъма за намиране на оптимална
 стратегия. Резултата от тази функция е максималната разлика между
 печалбата на играч 1 и играч 2. Естествено ако се максимизира тази
 разлика се максимизира и печалбата на играч 1, защото сумата на двете
 печалби е константа - 20.
 minimax алгоритъмът може по-лесно да се имплементира като вместо
 горната формула се използва еквивалентната:

    V(x) = MAX { Di - V(Ci) }
    V(x) = 0, ako се намираме в терминална конфигурация.

 Очевидно при нея всеки се опитва да максимизира собствената си
 печалба и да минимизира тази на другия.
 За да намерим начина на игра трябва да си пазим и с кои ход се
 постига оптимума на съответната функция.
 Естествения начин за реализиране на minimax процедурата е рекурсия.
 Лесно се съобразява, че трябва да използваме таблица за запаметяване
 на решенията, защото от две различни конфигурации можем да попаднем
 в една и съща, и би било неефективно да преизчисляваме наново
 оптималната стратегия. Всяка конфигурация може да бъде кодирана
 като число в 6-чна бройна система (защото се съобразява, че
 максималния брой на зърната във всяка дупка е 5, а минималния - 0),
 което ни помага за по-лесното организиране на таблицата.

 Петко Минков
*/
#include <fstream.h>

#define SIZE    7
#define INF     1024
#define SPACE   280000

struct state {
  int c[SIZE];

  int code();
  void decode(int);
};

int table[SPACE];
int move[SPACE];

/*
 Кодиране и декодиране на състоянието на играта
 */
int state::code()
{
  int i, cod;

  cod = 0;
  for(i = 0; i < 7; i++)
    cod = cod * 6 + c[i];

  return cod;
}

void state::decode(int cod)
{
  int i;
  
  for(i = 0; i < 7; i++)
  {
    c[i] = cod % 6;
    cod /= 6;
  }
}

/*
 Изиграва взимането на зърната от дупка i и връща
 дъската резултат в t.
 */
int playstate(state s, int i, state &t)
{
  int inhand, win = 0;
  
  t = s;
  inhand = t.c[i];
  t.c[i] = 0;
  i++; i %= SIZE;

  while(inhand)
  {
    if(inhand > 1)
    {
      if(t.c[i] == 5)
      {
        t.c[i]--;
        win++;
      }
      else
      {
        inhand--;
        t.c[i]++;
      }
    }
    else
    {
      if(1 <= t.c[i] && t.c[i] <= 4)
      {
        win += t.c[i] + 1;
        t.c[i] = 0;
        inhand = 0;
      }
      else
      {
        inhand--;
        win--;
      }
    }
    i++; i %= SIZE;
  }

  return win;
}

/*
 Изчисляване на оптимална стратегия с minimax алгоритъм.
 */
int calcgame(state s)
{
  int i, val, optval, scode;
  state t;
  
  scode = s.code();
  if(table[scode])
    return table[scode];
  
  optval = -INF;
  for(i = 0; i < 7; i++) if(s.c[i])
  {
    val = playstate(s, i, t) - calcgame(t);
    if(val > optval)
    {
      optval = val;
      move[scode] = i;
    }
  }

  if(optval == -INF)
    optval = 0; /* достигнали сме терминална конфигурация */
  return table[scode] = optval;
}

/*
 Функция която реализира комуникацията с опонента.
 */
void playgame(state s, int pl)
{
  int scode;
  state t;
  
  scode = s.code();
  if(!move[scode]) return;
  if(pl == 0)
    cout << move[scode] + 1 << endl << flush;
  else
  {
    cin >> move[scode];
    move[scode]--;
  }
  playstate(s, move[scode], t);
  playgame(t, !pl);
}

void main()
{
  int i;
  state init;
  
  for(i = 0; i < 7; i++)
    cin >> init.c[i];

  calcgame(init);
  playgame(init, 0);
}