Scratch

Hardmath123 wrote:

EDIT: Kind of unrelated, but where can I find the .py source of the modules? I can find all the pyc/pyo-optimized files, but I obviously can't read those. 

if you have them, they're in the same place. if they aren't, you apparently don't have them 

Last edited by roijac (2012-11-11 10:41:06)

Hardmath123 wrote:

blob8108 wrote:

For the interface — it would be really nice for a human to be able to play against the AI whilst developing it, as well as watch the AIs play each other. How about an HTML/Ajax interface with a Twisted/Python backend? (I'll code the Twisted stuff...) We could have a simple HTTP interface returning JSON objects (or even use WebSockets!).

That's a wonderful idea! I've made Python backends with CGIHTTPServer...

No, no, you need to use Twisted. Seriously. I'm not backing down on this point 

How about division of labour? after all

I'm great with <Canvas> UIs, so we're good that way, too.

— so how about I do the Python backend, and you do the HTML/JS frontend?    We just need to agree on the interface!

We could use AJAX queries like MOVE.py?player=hardmath&boardpos=…. MOVE.py should be modified with the AIs added in.

That looks messy    Can't we at least use POST requests? And I think we should use jQuery, too, if you agree.

Also, we really need to pick a game soon. Hex or Mancala would be my main choices, but both are biased towards the first mover.

Either sounds good. I don't think the first mover bias matters too much; we can always alternate players. Kalah looks confusing; I'd need to try and understand it properly. We might as well do Hex, since we planned to before — but I really don't mind    you choose something!

EDIT: Kind of unrelated, but where can I find the .py source of the modules? I can find all the pyc/pyo-optimized files, but I obviously can't read those. 

Python source of what modules?

I'll answer in reverse order because simplicity of answers seems to go that way:

Python source of what modules?

Python source of all included (Pure Python) modules, ideally.

Either sounds good. I don't think the first mover bias matters too much; we can always alternate players. Kalah looks confusing; I'd need to try and understand it properly. We might as well do Hex, since we planned to before — but I really don't mind    you choose something!

Hex, then. 

No, no, you need to use Twisted. Seriously. I'm not backing down on this point.

Well that gives me a whole lot of choice, doesn't it? 

Actually, that sounds good. I'm not sure at all how Twisted works, but in the end I want to have:
1. A main server which I run in the background
2. A file which I view on localhost:****/Desktop/Hex/Hex.html: this one should echo back an HTML page I'll write you
3. A file in which I add multiple AIs which can be called
4. An API which given a board and an AI's name should return the coordinates of the move (using file 3).

Fair? I'll write up the JS and everything else. 

EDIT: I was bored, so I looked up the Twisted docs. It looks really cool, now I'm really excited. 

Last edited by Hardmath123 (2012-11-12 03:31:45)

ohaiderstudios wrote:

Rock Paper Scissors could be a fun one. You know, try to predict patterns...or just try to be as random as possible to confuse the opponent.

A lot more strategies than Prisoner's Dilemma IMHO

WRONG

in RPS, no strategy could defeat random, in PD every good strategy could

that's what i'm talking about 
http://en.wikipedia.org/wiki/Prisoner%27s_dilemma#Strategy_for_the_iterated_prisoners.27_dilemma

I think we can simplify that a little:

Since we're doing all the AI in Python, I can drastically rework (rewrite, basically  ) the HTML. When I have a move, here's what should happen:

JS sends an XHR POST request to aimove.py with a CGI encoding a) the board encoded as a sequence of 0,1,2; b) the AI to use.

aimove.py is a Twisted server that does something like this:

…
def render_POST(self,request):
    board = cgi.escape(request.args["board"][0])
    ai    = cgi.escape(request.args["ai-id"][0])
    import aiplayers
    move  = aiplayers.play(board,ai)
    return str(move[0])+"\n"+str(move[1])
…

Finally, the contestants should modify aiplayers by adding a method which takes a board as argument (ideally parsed into a list of lists) and returns a tuple of (X,Y) to move to.

#aiplayers should be something like this

def hm(board):
    # AI here
def bl(board):
    # AI here

aiList = {"hardmath123":hm,"blob8108":bl}
def play(board,ai)
    parsed = parse(board)
    return aiList[ai](board)

You make sense. Or the neighbors have finally succeeded in their long-standing attempt to drive me crazy (playing loud hard rock at 5AM: the perfect crime  ).

First, I want to point out that you really don't need to worry about how much JS I have to right: the UI will be really easy (unless I choose to use THREE.js+WebGL to make a cool 3D board, which I don't think I will). So we don't need to consider division of labour. 

Let's try to figure out what all tasks we need to do, and assign them to either server or JS:

1. GUI to play Hex: JS, obviously
2. Protocol and connection between server and JS: both
3. Maintenance of the board's data and move log: ???
4. AI players: Python
5. Move authentication and winner/loser detection: ???

I think it's clearly more sensible to maintain the board on the JS side. If we have the server keep persistent data between moves the entire code will be much more complicated. As you said, it'll also give us simultaneous games for free. Additionally, we need to give the JS the board data anyway, so we might as well keep it on the browser (unless we keep a copy of the board on each side and just send X/Y tuples; but that sounds like too much trouble and lots of possibilities for error.)

Move authentication is probably better kept on the JS side too, since I'll have to authenticate the humans' moves. Also, what happens if the Python does catch an invalid move? Error protocol? Ew.    The JS can handle it appropriately by either sending another call just to be safe, or automatically forfeiting the offending computer (that sounds so weird to say  ). This would be considered a part of  "interface", anyway, in my opinion since what if we play human-vs.-human mode?

By the same logic as above, we should ideally check for winner-loser detection on the JS-side, too, though I can think of a really beautiful recursive Pythonic definition right now based on pathfinding algorithms. I can probably pull it off in JS, so I'm fine.

If this really does take off, we could mount this on App Engine, it would be really awesome. 

Let's figure out a protocol: I think CGI-style stuff would be fine: ai=blah&boardpos=1011212010002102012...&aiplaysas=2. Something like that. Then we can get started with actual coding.

If you haven't already written everything in Twisted, bottle might be of some interest. Though it's mostly for websites/web applications. 

http://bottlepy.org/docs/dev/

Gevent might also be interest. I suggest looking at the entire front page.

http://www.gevent.org/

Well, that sounds ok, I guess. Here are my views:

Why is it better to use Python for all the "behind the scenes" stuff (board flipping, win testing, move authentication)? The biggest reason against is that we need to authenticate the human's move, too, and obviously we shouldn't bother sending that over to the server just to authenticate when we could be doing it locally. Instead, I think the JS should validate all moves, along with all other behind the scenes stuff.

We don't really need the board flipping code. Since we tell the AI whether to place a red or blue counter (1 or 2), we may as well just make a convention that blue plays top-to-bottom and red plays left-to-right.

Supporting JS AIs seems easy, but I think there are a bunch of catches, mainly that someone smart enough to code an AI is clearly smart enough to use scoping rules to his advantage and "cheat" with yucky code. I don't want to waste my time hacker-proofing my code, and besides, everyone who has said yes so far seems to have their hearts set on Python.

I definitely intended to have asynchronous move functions; but I'd rather use XHRs manually than resort to a big library like jQuery (I'm a minimalist). I'm actually going to use native DOM elements (DIVS, actually) for my Hex board, so I can have a single move/authenticate/detectwin function with wrappers to receive data from the AI or the human based on who's turn it is (a global boolean flag). This simplifies a lot of stuff.

On the Python side, I take back my idea about coding a single function, and would rather code a module AI script. This lets us define plenty of subroutines, as well as testing scripts which we can run without the server. You'd simply use something like __import__("Hardmath123") or import Hardmath123 as currentAI, though I'm not sure exactly how Python handles namespaces.

Overall, it's probably better if we each code our own side and agree on a "bridge" (the protocol). This will give us optimum code, without anything muddled.

EDIT: If I encode the board as a sequence of 0s, 1s and 2s, it makes sense to just convert it to base 3, which would have a max of about half the digits and min of 1 for obvious cases. I'll leave to back-to-sequence decoding to you in Python, but I think this will be helpful. If we have a sequence of n digits, then the worst case in base 3 would be n digits of 22222... which is 2*(3^0+3^1+3^2+...+3^(n-1)) or (3^n-1). The number of digits is about the log of this, which for n=100 amounts to 47.

EDIT2: Why do we communicate with walls of text on this thread? I'm almost feeling compelled to lengthen my posts just to keep up. 

Last edited by Hardmath123 (2012-11-13 12:23:33)

Hardmath123 wrote:

Why do we communicate with walls of text on this thread? I'm almost feeling compelled to lengthen my posts just to keep up. 

Because I (and nXIII too, apparently) reply to the things you say all at once.    In the interests of brevity, then:

I just thought it would be easier to use Python for the "hard" bits; I agree with you that it makes the protocol easier not to.

nXIII makes some good points. The one about validation — do we just assume that all code is trusted? Unless we have an actual server on the public internet (which would be awesome...  ) He also said some things about JS, which I'll leave for now...

We've discussed board flipping at least twice now! =P (Here's you sort-of agreeing with me.) So that every AI doesn't have to do this themselves: For an AI playing as red, we will flip the board before passing it to the AI. We can then flip the x,y co-ords that we get back. We don't need to tell the AI who to play as; all the AI code will assume blue. 

For the interface: if you POST to http://localhost:8000/ai/get_move with:

  * board_size = 17 (or whatever)
  * board = "0R00000BB00BRR..."
  * AI = "blob8108"

— you'll get back a JSON object {x: 5, y: 7} with the co-ords. Happy? (:

Please don't use base 3 encoding! It's a nice idea, but at only ~<300 characters it's not worth compressing, and it'll make the protocol much more complicated. I tried base64 in Scratch for that roads game, and never got it to work properly.

Each AI will be a Python class in its own file. I'll figure out how to find them.

jQuery isn't exactly big, and I'd have thought using it would make more minimal code; but it's your code, have fun    And how are you planning to make hexagons out of DOM elements?! Personally I'd use Raphael, too...

---

Right, I'm off to figure out how to sandbox Python code so we can run a public server that hosts the AIs, with user submissions... PyPy looks cool! 

[Edited to mildly increase brevity]

Last edited by blob8108 (2012-11-13 17:28:52)

I agree with Hardmath123: It will simplify everything if the program flips the board in between turns.  It would help the AI code as well, since a computer player would behave the same way whether playing black or white. 

Flipping isn't that hard to implement.  Let's say L1 and L2 are the indexes of the last items in each dimension of the array. 

Switch item array[i][j] with item array[L1 - i ][L2 - j]. 

array[5][5] = 
{
   { 01, 02, 03, 04, 05 },
   { 06, 07, 08, 09, 10 },
   { 11, 12, 13, 14, 15 }
   { 16, 17, 18, 19, 20 }
   { 21, 22, 23, 24, 25 }
}

L1 = 4, L2 = 4, because the array is 5 x 5, so the last element will be array[4][4].  The first index here represents vertical position in the code (since it's an array of arrays). 

Switch array[0][0] (01) and array[4][4] (25)
Switch array[1][3] (09) and array[3][1] (17)
Switch array[4][1] (22) and array[0][3] (04)
etc.

Last edited by amcerbu (2012-11-13 19:47:42)

Oh, whoops, guess I'm with blob8108.  I guess if we're doing it on a Hex board, made of triangles, flipping would be a little more complicated. 

According to Wikipedia, an 11 x 11 field is standard for Hex, but the game can also be played on 13 x 13 and 19 x 19, and theoretically a field of any size.  It would be interesting to experiment with different field sizes — perhaps some are more difficult than others.  It would also be entertaining to try 100 x 100 or something ridiculous like that.  But I firmly believe that field size should be a property that can be changed, and that isn't implementation-specific (size becomes another one of the variables "fed" to AI code).  A perfect AI should be able to play on a field of any size.

EDIT (important): I just ran across this, and I think it would be a good thing to add to our list of things to do.  Again, according to Wikipedia, the first player in a game of Hex has a distinct advantage.  That can be balanced by the use of the so-called "Pie Rule."  Basically, after Player 1 makes the first move of the game, Player 2 may opt to switch positions with Player 1 (but he doesn't have to).  If they do switch, the original Player 1 makes the second move of the game. 

Anyway, I think it would be worth implementing.  Another thing for the AI to chew on. 

http://en.wikipedia.org/wiki/Pie_rule

Last edited by amcerbu (2012-11-14 01:05:00)

Hexagons. What do you think?