Поигрался немножко на выходных с гадалкой и появилось непреодолимое желание ещё пофлудить в этой темке, хоть она, возможно, уже и успела уплыть за пределы актуальности.
2
IuraЦитата:
Нашел что искал - "Прогнозирование стохастических последовательностей"
Нашли что искать.
За мозгодробительными формулировками этой статьи, по-сути, скрывается оптимистичное заключение о разрешимости вашей задачи. Да и заканчивается она немного с черным юморком как-то, "Во время работы над этой статьей умер _ Колмогоров".
Цитата:
О, а мне понравился подход автора этой программульки с выбором оптимальных параметров гадалки (количества учитываемых ходов, как человека так и собственных).
К сожалению, на упомянутом вами ресурсе мне почему-то не удалось отыскать исходных текстов программы heshby (лично у автора исходники не выпрашивал, уж больно напугало меня его заявление о том, что "авторские права распространяются на использованный в программе алгоритм предикции стохастических процессов"), поэтому я все-таки попробую привести здесь возможный набросок реализации её алгоритма.
Но сначала напишу простейший неинтерактивный вариант гадалки (одна штука; учет двух ходов с каждой стороны), играющей против генератора псевдослучайных чисел и печатающей качество предсказания в процентах (пример на C):
#include <stdio.h>
#include <stdlib.h>
int S[2][2][3][3][2], a[3], b[3];
int main(void)
{
int i, *p, c=0;
for(i=0; i<350; i++)
{
p=S[a[1]] [a[2]] [b[1]] [b[2]];
a[0]=a[1]; a[1]=a[2]; b[0]=b[1]; b[1]=b[2];
if((a[2]=rand()%2)==(b[2]=p[0]==p[1]?2:p[0]<p[1])) c++;
p[a[2]]++;
}
printf("%d%%", 100*c/i);
return 0;
}
(Оффтоп)
Кстати, есть сомнения в правильности понимания мной алгоритма Гадалки Шеннона. Если что не так, поправьте меня, пожалуйста (человекочитабельный и обобщенный вариант, не страдающий от синдрома запиндюривания всего кода в одну строку, см. ниже).
(Оффтоп)
Младшие биты числа, возвращенного rand()'ом нешибко-то случайны. Увеличится ли "случайность" бит (эксперимент показывает, что да) если их значения получать по-прежнему как rand()%2, но предварительно делать ещё один вызов этой функции вхолостую, i.e. на деле использовать значение выражения (rand(), rand()%2)?
А вот пример (в этот раз на C++) предиктора на основе набора гадалок (с различными параметрами, и, соответственно, с различной предсказательной способностью относительно данной последовательности):
#include <deque>
#include <map>
#include <vector>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstdlib>
namespace Fun
{
int TossACoin() {return rand()%2;}
// "Abstract" predictor.
class cPredictor
{
public:
cPredictor():
CorrectPredictionsCount(0),
PredictionsCount(0),
PredictedValue(0) {}
int Predict() {return NewPrediction(0);};
void Correct(int RealBit)
{
if(PredictedBit()==RealBit) CorrectPrediction();
};
// Returns the rate (quality) of correct predictions.
int Rate() const
{
if(!PredictionsCount) return 0; // Prevent div by zero.
return 100*CorrectPredictionsCount/PredictionsCount;
}
protected:
void CorrectPrediction() {CorrectPredictionsCount++;}
int NewPrediction(int PredictedBit)
{
PredictionsCount++;
return PredictedValue=PredictedBit;
}
int PredictedBit() const {return PredictedValue;};
private:
int CorrectPredictionsCount, PredictionsCount, PredictedValue;
};
struct cCheater: cPredictor
{
int Predict() {return NewPrediction(TossACoin());};
};
class cDaemon: public cPredictor
{
public:
explicit cDaemon
(
int RealBits=2,
int PredictedBits=2,
// Factor of "forgetfulness."
float CorrectingFactor=1,
// Minimal difference between probabilities.
float Threshold=0
):
LastBits(RealBits+PredictedBits+2, 0),
CorrectingFactor(CorrectingFactor),
Threshold(Threshold) {}
// Returns the most probable value of the next bit.
int Predict()
{
// Forget old bits.
LastBits.pop_front();
LastBits.pop_front();
// Just find a desired value in the
// associative array Statistics.
return NewPrediction(Statistics[LastBits].Value(Threshold));
}
// Adjusts the statistical model.
void Correct(int RealBit)
{
if(PredictedBit()==RealBit) CorrectPrediction();
// Remember that current real bit follows
// the bits from LastBits.
// FIXME: Reference to Statistics[LastBits] can be cached.
Statistics[LastBits].Correct(RealBit, CorrectingFactor);
// Save (in stack-like LastBits) RealBit &
// PredictedBit for future use.
LastBits.push_back(RealBit);
LastBits.push_back(PredictedBit());
}
int Weight() const {return LastBits.size()-2;}
private:
// FIXME: How to "parametrize" this class with
// CorrectingFactor & Threshold?
class cPrediction
{
public:
cPrediction():
One(0),
Zero(0),
Increment(1) {}
void Correct(int Bit, float CorrectingFactor)
{
// This can improve (when CorrectingFactor>1)
// prediction quality by reducing the
// influence of very old bits.
Increment*=CorrectingFactor;
// Increase the probability of a given
// bit at the next trials.
Bit? One+=Increment: Zero+=Increment;
}
int Value(float Threshold) const
{
// Try to predict the next bit by comparing
// probabilities of each case.
if(One-Zero>Threshold) return 1;
if(Zero-One>Threshold) return 0;
return 2; // Uncertain result.
}
private:
float One, Zero, Increment, CorrectingFactor, Threshold;
};
// FIXME: There is a more efficient way to store these bits.
typedef std::deque<int> cBits;
// FIXME: A container std::map is too slow, use
// something like hash_map instead.
typedef std::map<cBits, cPrediction> cStatistics;
// The stochastic model of an input sequence.
cStatistics Statistics;
// Last bits, both real and predicted.
cBits LastBits;
float CorrectingFactor, Threshold;
};
// FIXME: What about multithreading?
class cSupervisor: public cPredictor
{
public:
explicit cSupervisor
(
int MaximalRealBits,
int MaximalPredictedBits,
bool OptimizeCorrectingFactor=false
)
{
// Create daemons with all possible
// values of the parameters.
// FIXME: Does the STL provide means to
// deal with Cartesian product?
for(int i=0; i<MaximalRealBits; i++)
for(int j=0; j<MaximalPredictedBits; j++)
if(OptimizeCorrectingFactor)
for(float k=1; k<2; k+=0.05)
Daemons.push_back(cDaemon(i, j, k));
else
Daemons.push_back(cDaemon(i, j));
}
int Predict()
{
// Find the best daemon and ask for prediction.
// FIXME: Function std:: max_element is very suitable here
// but it's so difficult to express appropriate
// comparison criterion...
return NewPrediction(std::accumulate
(
Daemons.begin(),
Daemons.end(),
(int)2,
Rating()
));
}
void Correct(int RealBit)
{
if(PredictedBit()==RealBit) CorrectPrediction();
// Simply dispatch RealBit to each daemon.
std::for_each
(
Daemons.begin(),
Daemons.end(),
std::bind2nd // Yes, it's currying.
(
std::mem_fun_ref(&cDaemon::Correct),
RealBit
)
);
}
private:
std::vector<cDaemon> Daemons;
struct Rating: std::binary_function<int, cDaemon, int>
{
Rating(): Rate(-1), Weight(0) {}
int operator () (int LastPrediction, cDaemon &Daemon)
{
int Rate=Daemon.Rate(),
Weight=Daemon.Weight(),
Prediction=Daemon.Predict();
if(Rate>this->Rate||Rate==this->Rate&&Weight<this->Weight)
{
// Store the best results.
this->Rate=Rate;
this->Weight=Weight;
return Prediction;
}
return LastPrediction;
}
private: int Rate, Weight;
};
};
}
N.B., это очень "тормознутая" реализация и предназначена только для демонстрации. Буду рад если кто-нибудь перепишет/исправит/доработает приведенный мной код.
Третий параметр (
CorrectingFactor) в конструкторе
cDaemon'а позволяет улучшить качество предсказания за счет забывания начала игры (значение параметра для этого должно быть немного больше единицы). Четвертый параметр (
Threshold) равен минимальной разнице между вероятностями значений следующего хода, т.е., если вероятности (частоты) различаются незначительно, то гадалка дает неопределнный ответ (по-умолчанию этот параметр равен нулю и неопределенный ответ дается только в случае полной равноправности ожидаемых значений предсказываемого хода).
Пример игры против ГПСЧ:
#include <iostream>
const int IterationsCount=350;
int main()
{
Fun::cSupervisor Supervisor(5, 5, true);
for(int Counter=0; Counter<IterationsCount; Counter++)
{
Supervisor.Predict();
Supervisor.Correct(Fun::TossACoin());
}
std::cout << "Prediction quality is "
<< Supervisor.Rate() << '%' << std::endl;
return 0;
}
В только что приведеном примере можно заменить
cSupervisor на
cCheater (i.e. предиктор, пытающийся угадать последовательность "подбрасыванием монетки") и убедиться, что при игре ГПСЧ vs. ГПСЧ качество угадывание составляет 50% (вполне логично). Также можно заменить
cSupervisor на
cDaemon и увидеть, что качество предсказаний уменьшилось (опять ожидаемый результат).
Пример игры против человека:
#include <iostream>
int main()
{
Fun::cSupervisor Supervisor(5, 5, true);
while(1)
{
int Prediction=Supervisor.Predict();
std::cout << "> ";
int Real;
std::cin >> Real;
Supervisor.Correct(Real);
std::cout << "Prediction: " << Prediction << std::endl;
}
return 0;
}
P.S.:
Немного отойду от основной темы. Все тот-же
ltwood, автор heshby, утверждает, что человеку обыграть его программку не так-то просто. Ok, согласен. Также программульке туго приходится против ГПСЧ. Это понятно. Но, мне кажется, простой способ почти честно обыграть heshby существует и он очень прост. Действительно, что если заставить играть гадалку против аналогичной гадалки, но инвертирующей свои предсказания?
То есть, чтобы победить, просто запускаем две копии программки и пытаемся предсказать с помощью одной из них предсказания другой, после чего вбиваем противоположный ответ в атакуемую гадалку.
Возможна ли такая стратегия (типа антигравитации Мюнхгаузена)?
В любом случае, представляется разумной концепция игры одного предсказателя против другого. В общем, что если написать некую функцию
Fun::Play(...), которая будет принимать в своих аргументах двух предсказателей и возвращать качество игры, ну допустим, первого из них? Можно, например, заставить играть
cCheater'а против себя:
Fun::Play(Fun::cCheater(), Fun::cCheater(), ...); или устроить поединок
cDaemon vs.
cCheater:
Fun::Play(Fun::cDaemon(10, 10), Fun::cCheater(), ...); или же организовать игру с человеком:
Fun::Play(Fun::cSupervisor(5, 5, true), Fun::сPerson()). Я не реализовал пока такую функцию из-за сложностей с неопределенными ответами (ответ 2).
P.P.S.:
Вообще, думаю, тема предсказания (экстраполяции) последовательностей далеко не исчерпывается простейшими алгоритмами вроде Гадалки Шеннона и дискуссия может быть продолжена.
(Оффтоп)
А нельзя ли темку двинуть в дискуссионные или в cs (после чего удалить эту просьбу
)?
05.03.2010, 12:09 
но само направление верное