Jump to content

This site uses cookies. By continuing to browse the site you are agreeing to our use of cookies. Find out more here. X
X


Photo

Graph Theory Proof of Concept - Artifical Intelligence


  • Please log in to reply
9 replies to this topic

#1 twitchyliquid64

twitchyliquid64

    Peace. Always.

  • Active Members
  • PipPipPipPipPipPip
  • 527 posts

Posted 04 February 2011 - 11:27 PM

Hi all,

This is a short program I wrote to demonstrate the power of graph theory and its potential in Autoit.


Posted Image

Ultimately, graph theory is about dynamically creating records about specific ‘things’ in your program, and mapping how they relate, to allow your program to make inferences and do something smart.

Credit must be given to toady for the idea, and for minor internal management (I used his string regexp expression, and some array popping) Here is his one: http://www.autoitscript.com/forum/topic/...rtificial-intelligence-bot-pat

I would encourage you to first download the script and try it out. Place nodes around the place, then use the link tool to link nodes of your choosing together. Then, press setup, choose the start and end nodes, then press go. Then the program will find the shortest path from start to end, traversing the links you created.

If you want to find out what graph theory is, I encourage you to look at the Wikipedia entry and Google ‘shortest path problem’.

LEMME KNOW OF YOUR OPINIONS/COMMENTS!!!

Downloads:
The Program: Attached File  Node Graph Simulator.au3   8.47KB   391 downloads
My Node-Graph Theory UDF (you will need it to run): Attached File  node_graph UDF.au3   7.7KB   405 downloads

Regards,

Hypoz.

Edited by hyperzap, 09 February 2011 - 02:40 AM.

ongoing projects:-firestorm: Largescale P2P Social NetworkCompleted Autoit Programs/Scripts: Variable Pickler | Networked Streaming Audio (in pure autoIT) | firenet p2p web messenger | Proxy Checker | Dynamic Execute() Code Generator | P2P UDF | Graph Theory Proof of Concept - Breadth First search







#2 spudw2k

spudw2k

    passionately misinformed

  • Active Members
  • PipPipPipPipPipPip
  • 1,334 posts

Posted 04 February 2011 - 11:53 PM

Wow, very cool! I'd like to see a network tool built around this. Thanks for sharing!

#3 twitchyliquid64

twitchyliquid64

    Peace. Always.

  • Active Members
  • PipPipPipPipPipPip
  • 527 posts

Posted 05 February 2011 - 11:09 PM

Wow, very cool! I'd like to see a network tool built around this. Thanks for sharing!


Thanks. I'm building a wikipedia relation algorithm ATM but after that I'll rewrite my p2p udf to use this for message routing.
ongoing projects:-firestorm: Largescale P2P Social NetworkCompleted Autoit Programs/Scripts: Variable Pickler | Networked Streaming Audio (in pure autoIT) | firenet p2p web messenger | Proxy Checker | Dynamic Execute() Code Generator | P2P UDF | Graph Theory Proof of Concept - Breadth First search

#4 tobject

tobject

    Adventurer

  • Active Members
  • PipPip
  • 124 posts

Posted 06 February 2011 - 07:01 AM

can this be used for a portfolio of stocks to decide which stock to remove and which to add to minimize losses or maximize gains?

#5 twitchyliquid64

twitchyliquid64

    Peace. Always.

  • Active Members
  • PipPipPipPipPipPip
  • 527 posts

Posted 07 February 2011 - 09:37 AM

I'm not sure how you would use this for that: that sounds more like dynamic thresholding (using standard deviation) and a genetic algorithm.
ongoing projects:-firestorm: Largescale P2P Social NetworkCompleted Autoit Programs/Scripts: Variable Pickler | Networked Streaming Audio (in pure autoIT) | firenet p2p web messenger | Proxy Checker | Dynamic Execute() Code Generator | P2P UDF | Graph Theory Proof of Concept - Breadth First search

#6 Manadar

Manadar

         

  • MVPs
  • 10,900 posts

Posted 07 February 2011 - 09:55 AM

This is based on this right: http://www.autoitscript.com/forum/topic/47161-artificial-intelligence-bot-path-finding/ ?

Might want to give credit.

#7 Mat

Mat

    43 38 48 31 30 4E 34 4F 32

  • MVPs
  • 5,070 posts

Posted 07 February 2011 - 02:06 PM

How about going through and adding the chinese postman / eulerian graphs solutions, and the minimum spanning trees algorithms... I was thinking about doing something just like it a while ago, but wanted to build in all kinds of fancy user interfaces which I suck at. The only thing I'd add though is being able to weight the arcs.

@tobject

You are looking at linear programming there, for which you need simplex. Here is what I use to do all the working for me. Since it has to print the workings, there is a lot in there that can be stripped (there is a fair bit of code for using the letters, and an extra row and column in the tableau.
AutoIt         
#AutoIt3Wrapper_Change2CUI=y #AutoIt3Wrapper_Res_LegalCopyright=Matt Diesel (Mat) 2010 - 2011 Local $iNumVars = 2 Local $sObjectiveVarName = "P" Local $aVarNames[$iNumVars] = ["x", "y"] Local $aSlackNames[$iNumVars] = ["s", "t"] Local $aMaxEquation[$iNumVars] = [-6, -8] Local $aSubjectTo[$iNumVars][$iNumVars + 1] = [[4, 3, 1500],[1, 2, 500]] _Simplex_Working($iNumVars, $sObjectiveVarName, $aVarNames, $aSlackNames, $aMaxEquation, $aSubjectTo) Func _Simplex_Working($iNumVars, $sObjectiveVarName, $aVarNames, $aSlackNames, $aMaxEquation, $aSubjectTo)     ; 1.1 :: Print it     Local $sProblem = "Maximise " & $sObjectiveVarName & " = "     For $i = 0 To $iNumVars - 1         $sProblem &= $aMaxEquation[$i] * -1 & $aVarNames[$i] & " + "     Next     $sProblem = StringTrimRight($sProblem, 3)     $sProblem &= @LF & "Subject to: " & @LF     For $n = 0 To $iNumVars - 1         $sProblem &= "    "         For $i = 0 To $iNumVars - 1             $sProblem &= $aSubjectTo[$n][$i] & $aVarNames[$i] & " + "         Next         $sProblem &= $aSlackNames[$n] & " = " & $aSubjectTo[$n][$iNumVars] & @LF     Next     ConsoleWrite($sProblem & @LF)     ; 2 :: Initial Tableau     $aTableau = _Simplex_CreateTableau($iNumVars)     ; 2.1 :: Headers     $aTableau[0][0] = "Basic var"     For $i = 1 To $iNumVars         $aTableau[$i][0] = $aSlackNames[$i - 1]     Next     $aTableau[$iNumVars + 1][0] = $sObjectiveVarName     For $i = 1 To $iNumVars         $aTableau[0][$i] = $aVarNames[$i - 1]     Next     For $i = 1 To $iNumVars         $aTableau[0][$iNumVars + $i] = $aSlackNames[$i - 1]     Next     $aTableau[0][$iNumVars * 2 + 1] = "Value"     ; 2.2 :: Values     For $n = 0 To $iNumVars - 1         For $i = 0 To $iNumVars - 1             $aTableau[$n + 1][$i + 1] = $aSubjectTo[$n][$i]         Next         For $i = $iNumVars To $iNumVars * 2             $aTableau[$n + 1][$i + 1] = 0         Next         $aTableau[$n + 1][$iNumVars + 1 + $n] = 1         $aTableau[$n + 1][$iNumVars * 2 + 1] = $aSubjectTo[$n][$iNumVars]     Next     For $i = 1 To $iNumVars         $aTableau[$iNumVars + 1][$i] = $aMaxEquation[$i - 1]     Next     For $i = $iNumVars To $iNumVars * 2         $aTableau[$iNumVars + 1][$i + 1] = 0     Next     ConsoleWrite(_Simplex_TableauToString($aTableau) & @LF)     Do         _Simplex_Next($aTableau)         ConsoleWrite(_Simplex_TableauToString($aTableau) & @LF)         ; 7.1 :: Check optimal     Until _Simplex_Optimal($aTableau)     ; 7.2 :: Print solution     Local $sSolution = "Solution: " & @LF     For $n = 0 To $iNumVars         $sSolution &= $aTableau[$n + 1][0] & " = " & $aTableau[$n + 1][UBound($aTableau, 2) - 2] & @LF     Next     $sSolution &= "Everything else = 0" & @LF     ConsoleWrite($sSolution) EndFunc Func _Simplex_Next(ByRef $aTableau)     Local $iPivotRow = -1     Local $iPivotCol = -1     ; 3 :: Get pivot col     Local $r = UBound($aTableau) - 1     For $c = 1 To UBound($aTableau, 2) - 1         If $iPivotCol < 0 Or $aTableau[$r][$c] < $aTableau[$r][$iPivotCol] Then $iPivotCol = $c     Next     ; 4 :: Get pivot row     $c = UBound($aTableau, 2) - 2     Local $iTheta     For $r = 1 To UBound($aTableau) - 2         $iTheta = $aTableau[$r][$c] / $aTableau[$r][$iPivotCol] ; Theta = Value / Pivot value         If $iTheta < 0 Then             $aTableau[$r][$c + 1] = "--"         Else             $aTableau[$r][$c + 1] = "Theta = " & $iTheta             If $iPivotRow < 0 Or $iTheta < $aTableau[$iPivotRow][$c] / $aTableau[$iPivotRow][$iPivotCol] Then $iPivotRow = $r         EndIf     Next     $aTableau[UBound($aTableau) - 1][UBound($aTableau, 2) - 1] = ""     $aTableau[0][UBound($aTableau, 2) - 1] = "Pivot: " & $iPivotRow & "," & $iPivotCol ;;;;;     ; leaves the basis:     $aTableau[$iPivotRow][0] = $aTableau[0][$iPivotCol]     ConsoleWrite(_Simplex_TableauToString($aTableau) & @LF)     ; 5 :: Divide row by pivot:     Local $iPivot = $aTableau[$iPivotRow][$iPivotCol]     For $c = 1 To UBound($aTableau, 2) - 2         $aTableau[$iPivotRow][$c] /= $iPivot     Next     ; 6 :: Zero other rows     Local $iTimes     For $r = 1 To UBound($aTableau) - 1         If $r = $iPivotRow Then ContinueLoop         $iTimes = $aTableau[$r][$iPivotCol] / $aTableau[$iPivotRow][$iPivotCol]         For $c = 1 To UBound($aTableau, 2) - 2             $aTableau[$r][$c] -= $iTimes * $aTableau[$iPivotRow][$c]         Next         $aTableau[$r][UBound($aTableau, 2) - 1] = StringFormat("[%d] = [%d] - (%d * [%d])", $r, $r, $iTimes, $iPivotRow)     Next     $aTableau[$iPivotRow][UBound($aTableau, 2) - 1] = StringFormat("[%d] = [%d] / %d", $iPivotRow, $iPivotRow, $iPivot) EndFunc   ;==>_Simplex_Next Func _Simplex_Optimal($aTableau)     Local $r = UBound($aTableau) - 1     For $c = 1 To UBound($aTableau) - 1         If $aTableau[$r][$c] < 0 Then Return False     Next     Return True EndFunc   ;==>_Simplex_Optimal Func _Simplex_TableauToString($aTableau)     Local $sRet = ""     For $r = 0 To UBound($aTableau) - 1         For $c = 0 To UBound($aTableau, 2) - 2             $sRet &= StringFormat("| %-10.10s", $aTableau[$r][$c])         Next         $sRet &= "| " & $aTableau[$r][UBound($aTableau, 2) - 1] & @LF     Next     Return $sRet EndFunc   ;==>_Simplex_TableauToString Func _Simplex_CreateTableau($iNumVars) ;~ Rows: $iNumVars + 2 ;~ Cols: $iNumVars * 2 + 2     Local $aTableau[$iNumVars + 2][$iNumVars * 2 + 3]     Return $aTableau EndFunc   ;==>_Simplex_CreateTableau


Mat

#8 twitchyliquid64

twitchyliquid64

    Peace. Always.

  • Active Members
  • PipPipPipPipPipPip
  • 527 posts

Posted 08 February 2011 - 11:53 AM

This is based on this right: http://www.autoitscript.com/forum/topic/47161-artificial-intelligence-bot-path-finding/ ?

Might want to give credit.


I will/have updated the main post.

True, I did draw inspiration and stringregexp from toady, but a breadth first search algorithm with unlimited edges is a world of difference to a star with heuristics and limited edges.

In any case I do owe credit to toady.
ongoing projects:-firestorm: Largescale P2P Social NetworkCompleted Autoit Programs/Scripts: Variable Pickler | Networked Streaming Audio (in pure autoIT) | firenet p2p web messenger | Proxy Checker | Dynamic Execute() Code Generator | P2P UDF | Graph Theory Proof of Concept - Breadth First search

#9 Manadar

Manadar

         

  • MVPs
  • 10,900 posts

Posted 08 February 2011 - 12:14 PM

I will/have updated the main post.

True, I did draw inspiration and stringregexp from toady, but a breadth first search algorithm with unlimited edges is a world of difference to a star with heuristics and limited edges.

In any case I do owe credit to toady.

I hear you and I agree. There are lots of changes in your script, but the likeness between your code and toady was quite apparent. I didn't actually compare number of lines or anything like that, so I had no idea how much there is actually alike. On behalf of toady, I thank you. 8) Maybe a link to his A* topic would both serve toady and anyone else looking for path finding algorithms.

#10 twitchyliquid64

twitchyliquid64

    Peace. Always.

  • Active Members
  • PipPipPipPipPipPip
  • 527 posts

Posted 09 February 2011 - 02:40 AM

I hear you and I agree. There are lots of changes in your script, but the likeness between your code and toady was quite apparent. I didn't actually compare number of lines or anything like that, so I had no idea how much there is actually alike. On behalf of toady, I thank you. 8) Maybe a link to his A* topic would both serve toady and anyone else looking for path finding algorithms.


Yea a link would help others lookin for path finding mechanisms.

Toadys A* is alot better for geometric purposes, cause it allows heuristics to influence the order of searching nodes, increasing speed.

However, you can only have max 8 neighbours and it only works when there are geometry relations, so its not good for dynamic things like networking.

Thats why I made this script; To develop my P2P UDF into an onion router.

(FULL STOP =])
ongoing projects:-firestorm: Largescale P2P Social NetworkCompleted Autoit Programs/Scripts: Variable Pickler | Networked Streaming Audio (in pure autoIT) | firenet p2p web messenger | Proxy Checker | Dynamic Execute() Code Generator | P2P UDF | Graph Theory Proof of Concept - Breadth First search




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users