Differences

This shows you the differences between two versions of the page.

--- public:t-622-arti-11-1:final_project [2011/04/23 00:04] – angelo
+++ public:t-622-arti-11-1:final_project [2024/04/29 13:33] (current) – external edit 127.0.0.1
@@ Line 7: / Line 7: @@
 	border-width: 3px;
 	border-spacing: 2px;
-	border-style: solid;
+	border-style: none;
 	border-color: black;
 	border-collapse: collapse;
@@ Line 15: / Line 15: @@
 	border-width: 1px;
 	padding: 4px;
-	border-style: solid;
+	border-style: none;
 	border-color: black;
 	background-color: white;
@@ Line 23: / Line 23: @@
 	border-width: 1px;
 	padding: 4px;
-	border-style: solid;
+	border-style: none;
 	border-color: black;
 	background-color: white;
@@ Line 582: / Line 582: @@
 <br>
 <span onclick="toggle('abstract13', 'project13')" id="project13" style="cursor:pointer;font-weight: bold">[More]</span>
+</td>
+</tr>
+<tr valign="top">
+<td align="center">
+<img src="_media/public:t-622-arti-11-1:arti-s2011-finalproject-mylla.png" height="200" width="400">
+</td>
+<td>
+<b>Title: </b>Morris Game / Mylla
+<br>
+<b>Author: </b>Sigurður Jökull Eydal Tómasson
+<br>
+<b>Abstract:</b>
+<br>
+I wanted to make a game playing agent for 9-men Morris game. And the game environment as well. For this project i looked into search algorithms and heuristics.
+<div id="abstract14" style="display:none">
+<p>
+I'm using a modified version of A* algorithm, but i came up with the implementation. I found someone who had already made Nine-Men's Morris here, altough i did not base my solution on it. I googled the rules for the game, and used the book AI : a modern approach for the A* algorithm.
+</p>
+<p>
+ programmed the game rules and the gui and made the game playable for humans. And then created a class which the program calls, which recieves the gamestate and returns an action. The search algorithm works by first generating the actions available for the player in the specific circumstances and then uses an evaluation function to simulate the other players move. In order to create a simulation of the gameplaying, and then it looks for paths that lead to mills.
+</p>
+<p>
+The game is essentially split into three parts.
+The player has to choose coordinates to place their piece on, if he gets a mill he has to choose which of the other players pieces he removes. And he also has to move his own pieces.
+There are 4 things i took into consideration:
+<ol>
+<li>The Forming of mills;
+<li>Half-formed mills;
+<li>Forming of enemy mills;
+<li>Relative mobility.
+</ol>
+<br>
+So the player tries to maximize the forming of mills and mobility and minimize forming of enemy mills.
+</p>
+<p>
+It feels like you're playing against someone so i feel i have achieved to create a player that reacts correctly in basic circumstances, but the algorithm can still make stupid mistakes, i think some more fine-tuning would improve it.
+I'm happy with the resulting program but i would have liked to look at even more ways ways of doing this, for instance using machine learning to train a system to play the game. Or looking at more search algorithms.
+</p>
+</div>
+<br>
+<span onclick="toggle('abstract14', 'project14')" id="project14" style="cursor:pointer;font-weight: bold">[More]</span>
+</td>
+</tr>
+<tr valign="top">
+<td align="center">
+<img src="_media/public:t-622-arti-11-1:arti-s2011-finalproject-winappsalysis.jpg" height="200" width="400">
+</td>
+<td>
+<b>Title: </b>Ascr: Windows Process Analysis
+<br>
+<b>Author: </b>Sindri Bjarnason
+<br>
+<b>Abstract:</b>
+<br>
+The Ascr project itself is a console application in C++, below is a screenshot of the default
+execution process with some additional paint strokes for "illustrative" purposes.
+<div id="abstract15" style="display:none">
+<p>
+The default execution consists of the following operations:
+<ul>
+<li>Find and map to memory the training executable (SimpleCPP.exe);
+<li>Scan the training executable and decompose the PE structure;
+<li>Do a dumb scan of the file in memory and determine the boundary in which there is a high
+probability of executable code being present;
+<li>Generate “patterns”, which are simple subsets of the executable code sequence;
+<li>If successful, execute the training program and attach to its process using the Debug API.
+Attempt to match those patterns in the process memory.
+</ul>
+</p>
+<p>
+We distinguish between two different approaches to binary analysis, based on whether we
+are dealing with programs as a sequence of instructions stored in a physical file or as a process
+containing those instructions along with any runtime information required. For physical files, the
+approach is denoted as static analysis, and dynamic analysis for process analysis. In both cases, we
+are interested in determining the functionality of the binary through some form of analysis. In this
+project we tried to determine the functionality of Windows processes that originated from PE files
+(Portable Executables).
+</p>
+<p>
+Originally my approach was to focus solely on information available during runtime of the
+process, however, as it turns out that method is sub optimal since the volume of data retrieved
+expands too rapidly.
+</p>
+<p>
+There is plenty of research material available on the topic of binary analysis, the following
+are the relevant ones to this project:
+<ol>
+<li>Creating a basic debugger: <a href="http://msdn.microsoft.com/en-us/library/ms679288(v=VS.85).aspx">http://msdn.microsoft.com/en-us/library/ms679288(v=VS.85).aspx</a>. The Debug API interface from Microsoft;
+<li>An in-depth look into the Win32 Portable Executable Format: <a href="http://msdn.microsoft.com/en-us/magazine/cc301805.aspx">http://msdn.microsoft.com/en-us/magazine/cc301805.aspx</a>. The most detailed description of the Windows PE format;
+<li>Carbon based lifeforms – Set theory: <a href="http://www.youtube.com/watch?v=23iuPKuPd30&feature=related">http://www.youtube.com/watch?v=23iuPKuPd30&feature=related</a>. A solid tune;
+<li>X86 instruction set (intel): <a href="http://ref.x86asm.net/coder64">http://ref.x86asm.net/coder64">http://ref.x86asm.net/coder64">http://ref.x86asm.net/coder64</a>. A quite comprehensive html resource about the intel instruction set and the decoding process;
+<li>Beaengine: A library for decoding Intel instructions.
+</ol>
+</p>
+<p>
+The Ascr initially was built around the Debug API from Microsoft and has a functional
+debugger interface within the project file. A debugger is not a functional analyzer on its own, so it
+became apparent that references from the original PE file were needed. At that point, I focused
+my efforts on writing a parser for PE executables, using the MSDN article above.
+The main result is a conjecture which appears to hold for the simple training executable. It
+can be explained a bit formally as follows:
+Let sj be a sequence of instructions, such that si ϵ Ppe and si = { oj, oj+1, … , oj+n }. Let ν denote
+the variance of sj for all j's, ν = [0 … 1]. The variance is a measurement to the stability of the
+sequence sj in terms of the path through sj during runtime execution.
+A sequence sn has ν = 0, iff for all oi ϵ sn, we can predict the exact path through sn and the
+state of Prt at all times. A trivial example would be a nop sled or no-operations:
+snop = { 0x90, 0x90, … , 0x90 } <=> Prt = { i+1, i+2, …, i+n }, ν(snop) = 0.
+For all “first generation” sequences with ν = 0, we can map them directly to a set Ppe' = { D1,
+D2, … , Dn }, where Di is a higher-level representation of that sequence. For other sequences with ν
+> 0, we apply the following algorithm:
+<br>
+Let sk be a sequence where ν(sk) > 0 and |sk| > α, α is the largest single instruction. Then we
+have an index Δ, such that sk = { o1, o2, … , oΔ , … , on } => s'k = { o1, o2, … , oΔ } and ν(s'k) = 0,
+s''k = {oΔ , … , on } and ν(s''k) > 0. Since ν(s'k) = 0, mapping sk into Ppe' is based on determining
+the functionality of s''k. We know the entry to s''k from s'k from our Δ value and first try to
+see if we can reiterate this procedure on s''k, which if successful means that s''k is a new
+pattern. Since we are not emulating s''k our algorithm is complete. It will return two
+different sets, A and B. A contains the patterns for which ν = 0 and B the patterns for which
+ν > 0. The set B is the source of all the variance in Ppe. By isolating that set, we can focus
+the Ascr runtime analysis on those patterns, since by our conjecture, we can already
+resolve for A.
+Essentially, dynamic analysis boils down to analysis on the set B, which Ascr tried to
+accomplish through knowledge based engineering of the data gathered when executing the
+patterns of B. However, I did not have enough time to see it happen.
+</p>
+</div>
+<br>
+<span onclick="toggle('abstract15', 'project15')" id="project15" style="cursor:pointer;font-weight: bold">[More]</span>
+</td>
+</tr>
+<tr valign="top">
+<td align="center">
+<img src="_media/public:t-622-arti-11-1:arti-s2011-finalproject-contractbridge.jpg" height="200" width="200">
+</td>
+<td>
+<b>Title: </b>STRIPS planning for Contract Bridge bidding
+<br>
+<b>Authors: </b>Árni St. Sigurðsson, Baldur Blöndal, Pétur Ólafur Aðalgeirsson
+<br>
+<b>Abstract:</b>
+<br>
+We want to try using STRIPS-like operators to make descriptive bids for a given bridge hand and bid history.
+<div id="abstract16" style="display:none">
+<p>
+To our knowledge this is a fresh approach to the problem.
+</p>
+<p>
+We managed to implement lazy-evaluation to structure bidding conventions.  We made a robot class that was convention-card-abstract and a convention-card class representing the bid system.  Each bid would carry with it an implication for the cards in hand.  We did not make an inference engine to infer the implication.  We used reflective Python programming heavily.
+</p>
+<p>
+We realized that we should modify the robot to pass the hand *and the bid history* to the convention card functions for evaluation but lacked time to implement such deep surgery.
+</p>
+</div>
+<br>
+<span onclick="toggle('abstract16', 'project16')" id="project16" style="cursor:pointer;font-weight: bold">[More]</span>
 </td>
 </tr>