Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Complexity improvement for fictitious play #203

Closed
wants to merge 2 commits into from
Closed

Complexity improvement for fictitious play #203

wants to merge 2 commits into from

Conversation

louisabraham
Copy link

close #202

passes the tests

from time import time
import numpy as np

from nashpy.learning.fictitious_play import fictitious_play, fictitious_play2

shape = (2000, 2000)
n_iter = 100
A = np.random.rand(*shape)
B = np.random.rand(*shape)

d = time()
gen = fictitious_play(A, B, n_iter)
for play_count in gen:
    pass
print(time() - d, "s")

d = time()
gen = fictitious_play2(A, B, n_iter)
for play_count in gen:
    pass
print(time() - d, "s")
0.23587727546691895 s
0.005759000778198242 s

@drvinceknight
Copy link
Owner

0.23587727546691895 s
0.005759000778198242 s

Awesome!

Tests are probably going to fail for this as there are unit tests for some of the methods you have removed.

@louisabraham
Copy link
Author

My bad, I didn't retest after refactoring. This should be fixed now.

I guess that stochastic fictitious play could benefit from the same optimization but I will leave it for others!

@drvinceknight
Copy link
Owner

The CI is currently failing due to black:

tox: py38
[20](https://github.com/drvinceknight/Nashpy/actions/runs/4342077665/jobs/7582544619#step:6:21)
  py38: commands[0]> python -m black --check src/
[21](https://github.com/drvinceknight/Nashpy/actions/runs/4342077665/jobs/7582544619#step:6:22)
  would reformat /home/runner/work/Nashpy/Nashpy/src/nashpy/integer_pivoting/integer_pivoting_lex.py
[22](https://github.com/drvinceknight/Nashpy/actions/runs/4342077665/jobs/7582544619#step:6:23)
  would reformat /home/runner/work/Nashpy/Nashpy/src/nashpy/learning/fictitious_play.py
[23](https://github.com/drvinceknight/Nashpy/actions/runs/4342077665/jobs/7582544619#step:6:24)
  would reformat /home/runner/work/Nashpy/Nashpy/src/nashpy/learning/stochastic_fictitious_play.py
[24](https://github.com/drvinceknight/Nashpy/actions/runs/4342077665/jobs/7582544619#step:6:25)
  would reformat /home/runner/work/Nashpy/Nashpy/src/nashpy/repeated_games/__init__.py
[25](https://github.com/drvinceknight/Nashpy/actions/runs/4342077665/jobs/7582544619#step:6:26)
  
[26](https://github.com/drvinceknight/Nashpy/actions/runs/4342077665/jobs/7582544619#step:6:27)
  Oh no! 💥 💔 💥
[27](https://github.com/drvinceknight/Nashpy/actions/runs/4342077665/jobs/7582544619#step:6:28)
  4 files would be reformatted, 17 files would be left unchanged.
[28](https://github.com/drvinceknight/Nashpy/actions/runs/4342077665/jobs/7582544619#step:6:29)
  py38: exit 1 (0.43 seconds) /home/runner/work/Nashpy/Nashpy> python -m black --check src/ pid=1863

If you update black locally you should be able to reformat the two files.

A note on the work done:

  • Could you modify get_best_response_to_play_count and update_play_count in place as opposed to getting rid of them. This helps with testing/modularisation and readability (for example here I'm having to work a tiny bit harder to fully grep how what you have done is equivalent to what is there). This could also help with your suggestion of extending to stochastic_fictitious_play.
  • play_counts1, play_counts2: I don't believe we need to move to this pair of variables as opposed to the current play_counts where play_counts[0] and play_counts[1] correspond to those two variables. There's a couple of other spots where this change has happened but I don't believe it's necessary.

drvinceknight
drvinceknight requested changes Mar 6, 2023
View reviewed changes
src/nashpy/learning/fictitious_play.py
payoff1 = A @ play_counts2
payoff2 = play_counts1 @ B

A_t = A.T
Copy link
Owner

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
A_t = A.T
A_transpose = A.T

@drvinceknight drvinceknight changed the title fast fp Complexity improvement for fictitious play Mar 6, 2023
@drvinceknight
Copy link
Owner

I'm going to close this, feel free to reopen if you'd like to continue working on it.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@drvinceknight drvinceknight drvinceknight requested changes

Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

massive complexity improvement for fictitious play
2 participants
@louisabraham @drvinceknight