Моя алгоритам за играта 1-2-3 от първия кръг на конкурса по програмиране организиран от PCMagazine и Телерик.

След като разгледах решенията на поредния кръг от седемнадесето издание на най-престижният частен конкурс по програмиране, организиран от PC Magazine Bulgaria и Telerik.И за пореден път не видях никой друг да се възползва от пълните възможности на много ядрените процесори реших да публикувам решението с което спечелих ме първи кръг и да покажа колко лесно е да се ползват нишки за някои прости алгоритми.Условието на задачата може да намерите на този адрес игра 1-2-3.

В решението има няколко ключови момента които трябва да отбележа:

  1. За намиране на кои ход е най-добре да се изиграе се ползва рекурсия, но приемам че противника играе само най-добрите си ходове по този начин значително намалят разклоненията на рекурсията и съответно броя на изчисленията които са необходими.
  2. Използваме нишки за да възползвам от пълния капацитет на процесора.

Рекурсията

Първо намираме възможните ходове които може да играем.Това са всички ходове който ще ни дадат най-много точки.Примерно ако има 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/

Advertisements

има 1 коментар

Filed under .Net

Какво е качествен програмен код?

Какво е качествен програмен код?“-това определено е един доста интересен въпрос, които според мен има доста различни отговори. Предполагам че всеки един програмист на различен етап от своето развитие ще отговори различно освен ако не ползва готовите отговори от типа “код които се самоописва и е лесен за поддръжка“. Този отговор определено е верен но според мен не е достатъчен.

Всеки един програмист когато пише даден код и се старае да е качествен и добре подреден си мисли че е успял да постигне стандарта за качествен код. Но след няколко години  ако се върне и  разгледа кода си, винаги можеш да намери какво да подобри в него. Това се получава защото с годините човек трупа опит, а с опита се разширява представата за качествен код. В началото представата на всеки начинаещ програмист  за качествен код е само да се спазва конвенцията  и да се ползват методи. С напредването той разбира че,  е важно да се ползват класове и да се спазват ООП принципите –абстракция, наследяване, капсулация и полиморфизъм . В последствие започва да спазва инженерните похвати   strong cohesion и loose coupling  и да има преизползваемост на кода. И това ниво  е стандарта за качествен код за голяма част от програмистите, защото кода позволява на един средно добър програмист да разбере и доста бързо да навлезе в проектите. За програмистите така написания код се чете лесно и има нива на абстракция които му позволява по-лесно да навлиза в дълбочина без да се обърква или загубва в кода. Откарването и отстраняването на бъгове става сравнително лесно и доста бързо.Но според мен има още едно по-високо ниво на качеството на кода, но то става достъпно след много години практика в бранша, защото многото години опит развиват едно по-глобално мислене за проекта и неговите модули. Тези доста опитни софтуерни инженери правят кода  да не е  само лесен за поддръжка и разбиране но и лесен за добавяне на нова функционалност. Това става с ползването и разбирането на софтуерни похвати като дизайнерски шаблони (design patterns) .Ползването на такива шаблони за някой неопитни програмисти може да изглежда безсмислена загуба на време и усложняване на кода, но  в последствие може да спести доста време като се наложи да се правят по-сериозни промени или да се добави функционалност.

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

Вашият коментар

Filed under Developers