След като разгледах решенията на поредния кръг от седемнадесето издание на най-престижният частен конкурс по програмиране, организиран от PC Magazine Bulgaria и Telerik.И за пореден път не видях никой друг да се възползва от пълните възможности на много ядрените процесори реших да публикувам решението с което спечелих ме първи кръг и да покажа колко лесно е да се ползват нишки за някои прости алгоритми.Условието на задачата може да намерите на този адрес игра 1-2-3.
В решението има няколко ключови момента които трябва да отбележа:
- За намиране на кои ход е най-добре да се изиграе се ползва рекурсия, но приемам че противника играе само най-добрите си ходове по този начин значително намалят разклоненията на рекурсията и съответно броя на изчисленията които са необходими.
- Използваме нишки за да възползвам от пълния капацитет на процесора.
Рекурсията
Първо намираме възможните ходове които може да играем.Това са всички ходове който ще ни дадат най-много точки.Примерно ако има 5 хода в които можем да сложим по 3 букви това са ни възможните ходове. После пускаме рекурсия за всеки един от тях и оценяваме каква е вероятност да победим ако играем този ход.По този начин винаги намирам най-добрия ход.Проблема е, че за по голяма дъска има доста повече възможни ходове и се изисква доста повече изчисления които не могат да се направят в рамките на една секунда.А за намаляването на проблема идват на помощ нишките.
Нишки(Multithreading)
Това е една сравнително нова и доста често подценявана възможност за подобряваме скоростта на приложенията.Тази тема е доста сериозна и в добрите книги за програмиране може да има отделено място 200-300 страници.Но за някои прости алгоритми като този много лесно може да се ползват нишките без да е нужно да си много добър в тях.Основното нещо което трябва да се знае е, че ако имате едно множество от елементи на които трябва да се приложи някаква логика а резултата от тази логика не влияе на другите елементи в множеството много лесно може логиката да се реализира в нишки.Като за целта трябва да си направим статични всички елементи които искаме да са достъпни от всички нишки(в случая множеството) но трябва да си направим lock които заключва дадения общ ресурс за другите нишки докато една го ползва.По този начин се предпазваме от неприятни изненади като deadlock(една две нишки да се изчакват една друга да достопят даден ресурс и така да се блокират). Ето как си дефинираме lock и множеството:
static List<List<Coordinates>> listWithAllElemetsForRate;
static readonly object locker = new object();
Понеже на различните процесори има различен брои ядра които може да ползваме. И не може да дефинираме предварително някаква голяма бройка нишки защото те са скъп ресурс и ако процесора е с по-малко едра от колкото нишки сме натоварели на 100% може да има обратен ефект.Следващите редове код виждат колко ядра има процесора и стартират метода ThreadJoB толкова пъти в отделни нишки.
int numberOfCPUCores = Environment.ProcessorCount;
for (int i = 0; i < numberOfCPUCores; i++)
{
new Thread(ThreadJoB).Start();
}
Ето и самия метод в които ползваме locker.
static void ThreadJoB()
{
while (haveTime)
{
List<Coordinates> moveForChaeck;
lock (locker)
{
if (elementnumber < listWithAllElemetsForRate.Count)
{
moveForChaeck = listWithAllElemetsForRate[elementnumber];
elementnumber++;
}
else
{
break;
}
}
char[,] newMatrix = (char[,])matrix.Clone();
List<float> resultList = new List<float>();
foreach (Coordinates item in moveForChaeck)
{
newMatrix[item.Row, item.Col] = charPlay;
}
if (charPlay == ‘A’)
{
RecursionCheckMove(newMatrix, ‘B’, resultList);
}
else
{
RecursionCheckMove(newMatrix, ‘A’, resultList);
}
int score = MakeMoveSocre(resultList);
lock (locker)
{
if (score > bMove.moveScore)
{
bMove = new BestMove(score, moveForChaeck);
}
}
}
}
Като цяло нишките са доста полезни но и трябва да се внимава много с тяхното ползване защото крият и доста подводни камъни.Целия код на логическата част на играта може да бъде изтеглен от този svn: http://pcmagazine.googlecode.com/svn/trunk/
developerplace 